/*
 * Class Name:    RouteEst.java
 * Description:   TODO(类的功能描述)
 * Version:       2014年6月10日 下午6:43:42
 * Author:        Administrator
 * Copyright 2010 Cennavi Corp, All Rights Reserved.
 */
package com.cennavi.mm.service;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;
import java.util.concurrent.BlockingQueue;

import org.apache.commons.lang.StringUtils;
import org.apache.hadoop.hdfs.server.datanode.tail_jsp;

import redis.clients.jedis.HostAndPort;
import redis.clients.jedis.JedisCluster;

import java.io.Serializable;

import cn.com.cennavi.bean.DiDiNewData1;
import cn.com.cennavi.bean.DiDiOrignalBean;
import cn.com.cennavi.bean.DiDiTrajectory;
import cn.com.cennavi.bean.DifPointTotalMapInfo;
import cn.com.cennavi.dass.redis.RedisMasterSlave;
import cn.com.cennavi.dass.uti.DebugTools;

import com.cennavi.mm.astar.MicroSoftWAStar;
import com.cennavi.mm.astar.MircoSoftWMap;
import com.cennavi.mm.astar.Projection;
import com.cennavi.mm.thrift.GPS;
import com.cennavi.mm.thrift.RouteEstimationLink;
import com.cennavi.mm.util.MapUtil;
import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.Envelope;
import com.vividsolutions.jts.geom.Geometry;
import com.vividsolutions.jts.geom.LineSegment;
import com.vividsolutions.jts.geom.LineString;
import com.vividsolutions.jts.geom.Point;
import com.vividsolutions.jts.geom.Polygon;

/**
 * TODO(这里用一句话描述这个类的作用)
 * 
 * @author Administrator
 * @version 2014年6月10日 下午6:43:42
 */
public class RouteEstLocal implements Serializable {

	private JedisCluster jc;

	private HashMap<String, HashMap<String, String>> snodePreTrajMap = null;
	// // 随机读文件
	// private RandomCacheOper cellCacheOper = null;
	// private RandomCacheOper linkCacheOper = null;
	// private RandomCacheOper snodeCacheOper = null;
	private long jrCost = 0;
	private long rdCost = 0;
	private long jcTimes = 0;
	private long jrCost1 = 0;
	private long jcTimes1 = 0;
	private long jrCost2 = 0;
	private long jcTimes2 = 0;
	private long totalTimes = 0;
	// comma
	private static final String COMMA = ",";
	// seperate
	private static final String SEPERA = "$";
	// seperate
	private static final String SEPERB = "=";
	// cache网格默认数量
	public int cacheCellNum = 700000;
	// SeqNO
	public int seqNO = 0;
	// 匹配参数
	// 高频点候选匹配link数
	public static int projectionNum_HF = 6;
	// 低频点候选匹配link数
	public static int projectionNum_LF = 10;
	// 高频点平均回传周期上限，单位s
	public static int averageInterval = 10;
	// 高速道路速度阈值，限速系数，double型
	public static double speedFactor_HS = 1.5;
	// 低速道路速度阈值，限速系数，double型
	public static double speedFactor_LS = 1.5;
	// 低速道路限速上限，小于上限，单位km/h，double型
	public static double speedLimit = 90.0;
	// 左转cost，单位米，double
	public static double leftHandCost = 50.0;
	// 左转判断角度差，单位度，double型
	public static double leftHandAzimuthDis = 20.0;

	public static final String shardConfigFileName = "RedisShardingConfig";

	public static final String PRE_CELL = "C";
	public static final String PRE_LINK = "L";
	public static final String PRE_NODE = "N";

	// public static String cachePath = null;
	// public static String cacheBasePath = null;

	public static final DecimalFormat df = new DecimalFormat("##0.00");

	public RouteEstLocal(String shardConfig) throws IOException {
		String[] redisNoInfos = StringUtils.split(shardConfig, ",");
		Set<HostAndPort> jedisClusterNodes = new HashSet<HostAndPort>();
		for (String redisNoInfo : redisNoInfos) {
			String[] data = StringUtils.split(redisNoInfo, ":");
			if (data.length != 2) {
				continue;
			}
			try {
				jedisClusterNodes.add(new HostAndPort(new String(data[0]), Integer.parseInt(data[1])));
			} catch (Exception e) {
				DebugTools.println(redisNoInfo);
				continue;
			}

		}
		this.jc = new JedisCluster(jedisClusterNodes);
	}

	public RouteEstLocal(String redisCluster, HashMap<String, String> parameterMap, String uuid) {
		String[] redisNoInfos = StringUtils.split(redisCluster, ",");
		Set<HostAndPort> jedisClusterNodes = new HashSet<HostAndPort>();
		for (String redisNoInfo : redisNoInfos) {
			String[] data = StringUtils.split(redisNoInfo, ":");
			if (data.length != 2) {
				continue;
			}
			try {
				jedisClusterNodes.add(new HostAndPort(new String(data[0]), Integer.parseInt(data[1])));
			} catch (Exception e) {
				DebugTools.println(redisNoInfo);
				continue;
			}
		}
		this.jc = new JedisCluster(jedisClusterNodes);
		initParameter(parameterMap);
		// cacheBasePath = parameterMap.get("cachePath");
		// cachePath = parameterMap.get("cachePath") + File.separator + uuid;
		// createCacheFile(cachePath);
		// System.out.println("uuid:" + uuid + "|cacheCellNum:" +
		// parameterMap.get("cacheCellNum"));
	}

	// private void createCacheFile(String path) {
	// File dir = new File(path);
	// if (!dir.exists()) {
	// dir.mkdirs();
	// }
	// File[] files = dir.listFiles();
	// for (File file : files) {
	// file.deleteOnExit();
	// }
	// cellCacheOper = new RandomCacheOper(path + File.separator + "cell.dat");
	// linkCacheOper = new RandomCacheOper(path + File.separator + "link.dat");
	// snodeCacheOper = new RandomCacheOper(path + File.separator +
	// "snode.dat");
	// }

	// public String getCacheCellSize() {
	// return cellCacheOper.posMap.size() + "," + linkCacheOper.posMap.size() +
	// "," + snodeCacheOper.posMap.size();
	// }

	/**
	 * TODO(功能描述)
	 * 
	 * @param parameterMap
	 */
	private void initParameter(HashMap<String, String> parameterMap) {
		// TODO Auto-generated method stub
		if (parameterMap.containsKey("projectionNum_HF")) {
			projectionNum_HF = Integer.parseInt(parameterMap.get("projectionNum_HF"));
		}
		if (parameterMap.containsKey("projectionNum_LF")) {
			projectionNum_LF = Integer.parseInt(parameterMap.get("projectionNum_LF"));
		}
		if (parameterMap.containsKey("averageInterval")) {
			averageInterval = Integer.parseInt(parameterMap.get("averageInterval"));
		}
		if (parameterMap.containsKey("speedFactor_HS")) {
			speedFactor_HS = Double.parseDouble(parameterMap.get("speedFactor_HS"));
		}
		if (parameterMap.containsKey("speedFactor_LS")) {
			speedFactor_LS = Double.parseDouble(parameterMap.get("speedFactor_LS"));
		}
		if (parameterMap.containsKey("speedLimit")) {
			speedLimit = Double.parseDouble(parameterMap.get("speedLimit"));
		}
		if (parameterMap.containsKey("leftHandCost")) {
			leftHandCost = Double.parseDouble(parameterMap.get("leftHandCost"));
		}
		if (parameterMap.containsKey("leftHandAzimuthDis")) {
			leftHandAzimuthDis = Double.parseDouble(parameterMap.get("leftHandAzimuthDis"));
		}
		if (parameterMap.containsKey("cacheCellNum")) {
			cacheCellNum = Integer.valueOf(parameterMap.get("cacheCellNum"));
		}
	}

	public void close() {
		// cellCacheOper.close();
		// linkCacheOper.close();
		// snodeCacheOper.close();
		this.jc.close();
		// // 清除当前使用缓存文件
		// delPath(new File(cachePath));
		// // 清除map没有执行完的缓存文件
		// delOldFile(new File(cacheBasePath));
	}

	/**
	 * 删除路径
	 * 
	 * @param file
	 */
	public static void delPath(File file) {
		if (!file.exists()) {
			return;
		}
		if (file.isFile() || file.listFiles().length == 0) {
			file.delete();
		} else {
			File[] files = file.listFiles();
			for (File f : files) {
				delPath(f);
				f.delete();
			}
		}
	}

	/**
	 * 删除路径
	 * 
	 * @param file
	 */
	public static void delOldFile(File file) {
		if (!file.exists()) {
			return;
		}
		File[] files = file.listFiles();
		for (File fileStr : files) {
			try {
				int delNum = 0;
				File[] fs = fileStr.listFiles();
				for (File f : fs) {
					if ((System.currentTimeMillis() - f.lastModified()) > 24 * 60 * 60 * 1000) {
						f.delete();
						delNum++;
					}
				}
				if (delNum == fs.length) {
					fileStr.delete();
				}
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
	}

	public int getSeq() {
		seqNO = seqNO + 1;
		return seqNO;
	}

	// public void memoryChange() {
	// int cacheSize = cellCacheMap.size();
	// if (cacheSize >= cacheCellNum) {
	// int removeNum = Double.valueOf(cacheSize * 0.1d).intValue();
	// ArrayList<CellInfo> cellHitList = new ArrayList<CellInfo>(
	// cellHitMap.values());
	// Collections.sort(cellHitList);
	// for (int i = 0; i < removeNum; i++) {
	// CellInfo cell = cellHitList.get(i);
	// ArrayList<String> cellSnodelist = cellSnodeMap.get(cell.cellId);
	// if (cellSnodelist != null) {
	// for (String snode : cellSnodelist) {
	// snodePreTrajMap.remove(snode);
	// }
	// }
	// cellSnodeMap.remove(cell.cellId);
	// cellCacheMap.remove(cell.cellId);
	// cellHitMap.remove(cell.cellId);
	// }
	// }
	// }

	// public String printHitRange(String grid) {
	// double totalNum = hitNum + hitNotNum + 0d;
	// String range = df.format(hitNum / totalNum);
	//
	// return grid + "," + range + "," + hitNum + "," + totalNum;
	// }
	//

	public static List<GPS> filter(List<GPS> gps) {
		List<GPS> rst = new ArrayList<GPS>();
		// List<GPS> unsafe = new ArrayList<GPS>();
		if (gps.size() < 4) {
			return gps;
		}

		GPS last = gps.get(0);
		rst.add(last);
		last = gps.get(1);
		rst.add(last);
		// unsafe.add(gps.remove(0));
		int k = 1;
		// int k = 2;
		for (int i = 2; i < gps.size(); i++) {
			// for(int i=3;i<gps.size();i++){
			// if(i==54){
			// System.out.println("");
			// }
			GPS cur = gps.get(i);
			double a1 = MapUtil.azimuth(last.longtitude, last.latitude, cur.longtitude, cur.latitude);
			// 处理角度计算异常
			if (a1 < -180 || a1 > 180) {
				// System.out.println("Error azimuth:" + last.longtitude + " " +
				// last.latitude + " " + cur.longtitude + " " + cur.latitude);
				continue;
			}
			for (int j = k; j < i; j++) {
				GPS vet = gps.get(j);
				double a2 = MapUtil.azimuth(last.longtitude, last.latitude, vet.longtitude, vet.latitude);
				// 处理角度计算异常
				if (a2 < -180 || a2 > 180) {
					// System.out.println("Error azimuth:" + last.longtitude +
					// " " + last.latitude + " " + vet.longtitude + " " +
					// vet.latitude);
					continue;
				}

				double angle = Math.abs(a2 - a1);
				if (angle > 180) {
					angle = angle - 180;
				}
				// double err = dist * angle;

				if (angle > 10.0) {

					// System.out.println(dist);
					// if(angle>90){//U turn
					// rst.addAll(gps.subList(k, i-1));
					// }
					GPS v = gps.get(i - 1);
					double dist = MapUtil.calPointDistance(last.longtitude, last.latitude, v.longtitude, v.latitude);
					if (dist > 5) {
						// double azm = MapUtil.azimuth(last.longtitude,
						// last.latitude, v.longtitude, v.latitude);
						// v.setDirection(azm);
						rst.add(v);
						last = v;
						k = i;
						break;
					}
					// a1 = MapUtil.azimuth(last.longtitude, last.latitude,
					// cur.longtitude, cur.latitude);
				}
				double dist = MapUtil.calPointDistance(last.longtitude, last.latitude, vet.longtitude, vet.latitude);
				if (dist > 10) {
					// System.out.println();
					rst.add(vet);
					last = vet;
					k = j + 1;
					break;
				}
			}
			if (i == (gps.size() - 1)) {
				rst.add(cur);
			}
			// unsafe.add(cur);
		}
		// rst = rst.subList(80, 95);
		return rst;
	}

	public List<RouteEstimationLink> getRoute(TreeMap<Long, GPS> gpsMap, boolean boolFilter) throws Exception {
		if (this.snodePreTrajMap != null) {
			this.snodePreTrajMap.clear();
			this.snodePreTrajMap = null;
		}
		ArrayList<GPS> gpsList = new ArrayList<>();
		for (Map.Entry<Long, GPS> entry : gpsMap.entrySet()) {
			GPS gps=entry.getValue();
			gpsList.add(gps);
//			System.out.println("niuxinzan:queue:" + "MapMatchFunction2:" + gps.longtitude + "," + gps.latitude + "," + gps.direction + "," + gps.time + "," + (int) (gps.speed) + "," + DiDiNewData1.getDate(gps.time) );
		}
		int gpsInterval = getInterval(gpsList);
		// long t1 = System.currentTimeMillis();
		List<GPS> gpsSeq = boolFilter ? filter(gpsList) : gpsList;
		// long t2 = System.currentTimeMillis();
		// System.out.println("After filter gpsSeq:" + gpsSeq.size());
		Cell[] cells = new Cell[gpsSeq.size()];
		GPS lastgps = gpsSeq.get(0);
		for (int i = 0; i < gpsSeq.size(); i++) {
			GPS gps = gpsSeq.get(i);
			// String cell = MapUtil.findGlobalCell(gps.getLongtitude(),
			// gps.getLatitude());
			String cell = MapUtil.findCell(gps.getLongtitude(), gps.getLatitude());

			// Envelope env = MapUtil.getGlobalCellBound(cell);
			Envelope env = MapUtil.getCellBound(cell);
			Polygon polygon = MapUtil.getGPSPolygon(new Coordinate(gps.longtitude, gps.latitude), env);

			cells[i] = new Cell(gps, cell, polygon);
			// 用两点连线的方位角代替点GPS的角度
			if (i > 0) {
				double azm = MapUtil.azimuth(lastgps.longtitude, lastgps.latitude, gps.longtitude, gps.latitude);
				// 处理角度计算异常
				if (azm < -180 || azm > 180) {
					// System.out.println("Error azimuth:" + lastgps.longtitude
					// + " " + lastgps.latitude + " " + gps.longtitude + " " +
					// gps.latitude);
					continue;
				}
				lastgps.setDirection(azm);
				// 起始点用第二点的方位角近似
				if (i == (gpsSeq.size() - 1)) {
					gps.setDirection(azm);
				}
				lastgps = gps;
			}
		}
		// try {
		// Main.writePointShp(gpsSeq, "E:/shp/dd-p-f.shp");
		// } catch (Exception e2) {
		// // TODO Auto-generated catch block
		// e2.printStackTrace();
		// }
		long s1 = System.currentTimeMillis();
		try {
			readCell(cells, gpsInterval);
			this.snodePreTrajMap = getNodePreTrajMap(cells);
		} catch (Exception e1) {
			// TODO Auto-generated catch block
			// e1.printStackTrace();
			long c1 = System.currentTimeMillis() - s1;
			rdCost = rdCost + c1;
			throw new Exception(e1);
		}
		long c1 = System.currentTimeMillis() - s1;
		rdCost = rdCost + c1;
		// 保存读取的link信息
		HashMap<String, Link> linkIDLinkMap = getLintMap(cells);
		// 保存每条link上的投影信息
		HashMap<String, ArrayList<Projection>> linkProjMap = getLinkProjMap(cells);

		// DebugTools.println("Start getCaPaths:" + new Date().getTime());
		// // 得到所有可能的起点id所在的shard
		// HashMap<Integer, ArrayList<String>> shardNoNodeIDMap =
		// getShardNoNodeIDMap(cells);
		// DebugTools.println("Start getNodePreTrajMap:" + new
		// Date().getTime());
		// DebugTools.println("End getNodePreTrajMap:" + new Date().getTime());

		ArrayList<ArrayList<CaPath>> paths = new ArrayList<ArrayList<CaPath>>();
		Cell lastcell = cells[0];

		for (int i = 1; i < cells.length; i++) {
			if (lastcell.getPrj() == null || lastcell.getPrj().size() < 1) {
				lastcell = cells[i];
				continue;
			}
			Projection[] s = new Projection[lastcell.getPrj().size()];
			Cell cur = cells[i];
			if (cur.getPrj() == null || cur.getPrj().size() < 1) {
				continue;
			}

			Projection[] e = new Projection[cur.getPrj().size()];

			lastcell.getPrj().toArray(s);
			cur.getPrj().toArray(e);

			lastcell = cur;

			ArrayList<CaPath> p = getCaPaths(s, e, linkIDLinkMap);

			if (p.size() > 0) {
				paths.add(p);
			} else {
				// System.out.println(i);
			}

		}

		// System.out.println("End getCaPaths:" + new Date().getTime());
		//
		// System.out.println("Start MircoSoftWMap:" + new Date().getTime());
		MircoSoftWMap map = new MircoSoftWMap(paths);

		MicroSoftWAStar atar = new MicroSoftWAStar();
		ArrayList<CaPath> finalPath = new ArrayList<CaPath>();
		List<String> finalNodes = new ArrayList<String>();
		double cost = Double.MAX_VALUE;

		int max = 0;
		for (int i = 0; i < map.getStartNodes().size(); i++) {
			for (int j = 0; j < map.getEndNodes().size(); j++) {
				List<String> nodes = atar.find(map, map.getStartNodes().get(i), map.getEndNodes().get(j));
				if (atar.maxnode > max) {
					max = atar.maxnode;
				}
				if (cost > atar.getCost()) {
					cost = atar.getCost();
					// System.out.println(cost+"=>"+nodes);
					finalNodes = nodes;
				}
			}
		}
		// System.out.println("");
		for (int i = 1; i < finalNodes.size(); i++) {
			finalPath.add(map.getCaPath(finalNodes.get(i - 1), finalNodes.get(i)));
		}

		double lastLinkTravelDis = 0.0;
		long lastLinkGpsTime = 0l;
		ArrayList<RouteEstimationLink> lns = new ArrayList<RouteEstimationLink>();
		for (int i = 0; i < finalPath.size(); i++) {
			CaPath p = finalPath.get(i);

			// 轨迹长度
			double len = p.getPathsLength();

			// 轨迹时长
			long t = (p.getEd().getGps().getTime() - p.getSt().gps.getTime());
			if (t == 0) {
				t = 1;
			}

			// km/h
			long speed = Math.round((len / t) * 3.6);

			// // 道路起点到投影点行驶的时间
			// long ts = 0l;

			// 起点进入时间
			long startt = p.getSt().getGps().getTime() * 1000;

			// 起点路链行驶距离
			double clen = p.getSt().linkLenth - p.getSt().prjDistanceFormSNode;

			// if (!lns.isEmpty()) {
			// ts = (long)(p.getSt().getPrjDistanceFormSNode() /(len / t));
			// t+=ts;
			// len += p.getSt().getPrjDistanceFormSNode();
			// startt = p.getSt().getGps().getTime()*1000 - ts*1000;
			// clen = p.getSt().getLinkLenth();
			// }

			try {
				lns.add(new RouteEstimationLink(Long.parseLong(p.getSt().getLinkID()), (int) (clen), startt, (int) speed));

				if (p.getSt().getLinkID().equalsIgnoreCase(p.getEd().getLinkID())) {
					lastLinkTravelDis = p.getEd().prjDistanceFormSNode;
					lastLinkGpsTime = p.getEd().getGps().getTime();
					continue;
				}

				if (p.getPaths() != null) {
					ArrayList<CaPathLink> pa = p.getPaths();
					for (CaPathLink l : pa) {
						long ct = (long) ((clen / len) * t * 1000);
						// 中间路链行驶长度等于link长度
						lns.add(new RouteEstimationLink(Long.parseLong(l.getId()), (int) (l.getLength()), startt + ct, (int) speed));
						// System.out.println(l.getId()+":"+(p.getSt().getGps().getTime()*1000+ct-
						// ts*1000));
						clen += l.getLength();
					}
				}
				// if(clen>len){
				// System.out.println(clen+","+len+","+p.getSt().getLinkID()+"->"+p.getEd().getLinkID());
				// }
				long endt = startt + (long) ((clen / len) * t * 1000);
				// if(p.getSt().getLinkID().equalsIgnoreCase(p.getEd().getLinkID())){
				// endt = startt;
				// }

				// 结束link行驶长度等于link长度
				lns.add(new RouteEstimationLink(Long.parseLong(p.getEd().getLinkID()), (int) (p.getEd().getLinkLenth()), endt, (int) speed));

				lastLinkTravelDis = p.getEd().prjDistanceFormSNode;
				lastLinkGpsTime = p.getEd().getGps().getTime();
				// System.out.println(p.getEd().getLinkID()+":"+endt);
				// lns+=","+p.getEd().getLinkID();
				// lns.add(p.getEd().getLinkID());
			} catch (Exception e) {
				DebugTools.println(e.getMessage());
				continue;
			}
		}

		// String lnks = ","+last;
		ArrayList<RouteEstimationLink> lnks = new ArrayList<RouteEstimationLink>();
		if (lns.size() > 0) {
			RouteEstimationLink last = lns.get(0);
			for (int i = 1; i < lns.size(); i++) {
				// System.out.println(lns.get(i).getLinkID()+":"+lns.get(i).getEnterTime());
				if (lns.get(i).getLinkID() != last.getLinkID()) {
					if (lns.get(i).getEnterTime() < last.getEnterTime()) {
						lnks.clear();
						break;
					}
					long speed = Math.round(last.travelLength * 1.0 / (lns.get(i).enterTime - last.enterTime) * 1000 * 3.6);
					last.setSpeed((int) speed);
					last.projList = linkProjMap.get(String.valueOf(last.linkID));
					lnks.add(last);
					last = lns.get(i);
				}

				// last = lns.get(i);
				if (i == lns.size() - 1) {
					last.travelLength = (int) lastLinkTravelDis;
					long speed = Math.round(last.travelLength * 1.0 / (lastLinkGpsTime - last.enterTime / 1000) * 3.6);
					last.setSpeed((int) speed);
					last.projList = linkProjMap.get(String.valueOf(last.linkID));
					lnks.add(last);
				}
			}
		}
		// 投影到link的两端的舍弃
		// ArrayList<RouteEstimationLink> resultlnks=new
		// ArrayList<RouteEstimationLink>();
		// for(RouteEstimationLink lik:lnks){
		//
		// long linkID=lik.getLinkID();
		// // System.out.println("niuxinzan123:linkID"+linkID);
		// ArrayList<Projection> newproj=new ArrayList<Projection>();
		// ArrayList<Projection> proj=lik.projList;
		// for(Projection geoProj:proj){
		// double linkLen=geoProj.linkLenth;
		// double prjDistanceFormSNode=geoProj.prjDistanceFormSNode;
		// //
		// System.out.println("linkID:"+linkID+" 距離link距離"+prjDistanceFormSNode+" linklen:"+linkLen);
		// if(prjDistanceFormSNode==0||prjDistanceFormSNode==linkLen){
		//
		// continue;
		// }else{
		// newproj.add(geoProj);
		// }
		// }
		// if(newproj.size()!=0){
		// RouteEstimationLink newLik=new RouteEstimationLink(lik.getLinkID(),
		// lik.getTravelLength(), lik.getEnterTime(), lik.getSpeed());
		// newLik.projList=newproj;
		// resultlnks.add(newLik);
		// }
		// }
		return lnks;
	}

	/**
	 * TODO(功能描述)
	 * 
	 * @param cells
	 * @return
	 */
	private HashMap<String, Link> getLintMap(Cell[] cells) {
		// TODO Auto-generated method stub
		HashMap<String, Link> linkMap = new HashMap<String, Link>();
		for (Cell cell : cells) {
			for (Link link : cell.getCellLinkIDs()) {
				linkMap.put(link.id, link);
			}
		}
		return linkMap;
	}

	/**
	 * TODO(功能描述)
	 * 
	 * @param gpsList
	 * @return
	 */
	private int getInterval(List<GPS> gpsList) {
		// TODO Auto-generated method stub
		Long timedis = gpsList.get(gpsList.size() - 1).time - gpsList.get(0).time;
		return (int) (timedis / (gpsList.size() - 1));
	}

	/**
	 * TODO(功能描述)
	 * 
	 * @param cells
	 * @return
	 */
	private HashMap<String, ArrayList<Projection>> getLinkProjMap(Cell[] cells) {
		// TODO Auto-generated method stub
		HashMap<String, ArrayList<Projection>> linkProjMap = new HashMap<String, ArrayList<Projection>>();
		for (Cell cell : cells) {
			ArrayList<Projection> prj = cell.getPrj();
			if (prj == null) {
				continue;
			}
			for (Projection projection : prj) {
				String linkID = projection.getLinkID();
				if (linkProjMap.containsKey(linkID)) {
					linkProjMap.get(linkID).add(projection);
				} else {
					ArrayList<Projection> projs = new ArrayList<Projection>();
					projs.add(projection);
					linkProjMap.put(linkID, projs);
				}
			}
		}
		return linkProjMap;
	}

	/**
	 * TODO(功能描述)
	 * 
	 * @param cells
	 * @return
	 */
	private HashMap<String, HashMap<String, String>> getNodePreTrajMap(Cell[] cells) {
		HashMap<String, HashMap<String, String>> snodePreTrajMap = new HashMap<String, HashMap<String, String>>();
		for (Cell cell : cells) {
			ArrayList<Projection> pros = cell.getPrj();
			for (Projection projection : pros) {
				totalTimes++;
				String nodeID = projection.enode;
				if (snodePreTrajMap.containsKey(nodeID)) {
					continue;
				}
				Position pos = null;
				// Position pos = snodeCacheOper.posMap.get(nodeID);

				if (pos != null) {
					// // long j1 = System.currentTimeMillis();
					// byte[] snodeBs = snodeCacheOper.getData(pos);
					// String[] snodes = StringUtils.split(new String(snodeBs),
					// "\\$");
					// HashMap<String, String> preTraj = new HashMap<String,
					// String>();
					// for (String snode : snodes) {
					// String[] item = StringUtils.split(snode, "=");
					// preTraj.put(new String(item[0]), new String(item[1]));
					// }
					// // long jc1 = System.currentTimeMillis() - j1;
					// // jrCost = jrCost + jc1;
					// jcTimes++;
					// snodePreTrajMap.put(nodeID, preTraj);
				} else {
					String key = RouteEstLocal.PRE_NODE + nodeID;
					try {
						// long j2 = System.currentTimeMillis();
						// HashMap<String, String> preTraj = (HashMap<String,
						// String>) this.jc
						// .hgetAll(key);
						// long jc2 = System.currentTimeMillis() - j2;
						// jrCost2 = jrCost2 + jc2;
						// jcTimes2++;
						HashMap<String, String> preTraj = (HashMap<String, String>) this.jc.hgetAll(key);
						if (preTraj != null) {
							snodePreTrajMap.put(nodeID, preTraj);
							// if (cellCacheOper.posMap.size() <= cacheCellNum)
							// {
							// // long j1 = System.currentTimeMillis();
							// // // 写入缓存数据
							// // snodeCacheOper.writeData(nodeID,
							// // getCacheData(preTraj));
							// // long jc1 = System.currentTimeMillis() - j1;
							// // jrCost1 = jrCost1 + jc1;
							// jcTimes1++;
							// // 写入缓存数据
							// snodeCacheOper.writeData(nodeID,
							// getCacheData(preTraj));
							// }
						}
					} catch (Exception e) {
						continue;
					}
				}
			}
		}

		return snodePreTrajMap;
	}

	/**
	 * TODO(功能描述)
	 * 
	 * @param shardNoNodeIDMap
	 * @return
	 */
	// private HashMap<String, HashMap<String, String>> getNodePreTrajMap(
	// HashMap<Integer, ArrayList<String>> shardNoNodeIDMap) {
	// // TODO Auto-generated method stub
	// HashMap<String, HashMap<String, String>> resultMap = new HashMap<String,
	// HashMap<String, String>>();
	//
	// // 并行读取网格包含的link序列
	// int threadCount = shardNoNodeIDMap.keySet().size();
	// CountDownLatch rlatch = new CountDownLatch(threadCount);
	// for (Integer shardNo : shardNoNodeIDMap.keySet()) {
	// RedisReaderThread thread = shardingReaderThreadMap.get(shardNo);
	// if (thread == null) {
	// thread = new RedisReaderThread(shardNo);
	// shardingReaderThreadMap.put(shardNo, thread);
	// }
	// thread.setCountDownLatch(rlatch);
	// thread.setReadFlag(CNConfig.READ_PRETRAJ);
	// thread.setSnodeIDArray(shardNoNodeIDMap.get(shardNo));
	// new Thread(thread).start();
	// }
	// try {
	// rlatch.await();
	// } catch (InterruptedException e1) {
	// // TODO Auto-generated catch block
	// System.out.println("rlatch.await() error!");
	// return null;
	// }
	// for (Integer shardNo : shardNoNodeIDMap.keySet()) {
	// RedisReaderThread thread = shardingReaderThreadMap.get(shardNo);
	// resultMap.putAll(thread.getSnodePreTrajMap());
	// thread.clear();
	// }
	// return resultMap;
	// }

	/**
	 * TODO(功能描述)
	 * 
	 * @param cells
	 * @return
	 */
	// private HashMap<Integer, ArrayList<String>> getShardNoNodeIDMap(Cell[]
	// cells) {
	// HashSet<String> nodeIDSet = new HashSet<String>();
	// HashMap<Integer, ArrayList<String>> resultMap = new HashMap<Integer,
	// ArrayList<String>>();
	//
	// for (Cell cell : cells) {
	// ArrayList<Projection> pros = cell.getPrj();
	// for (Projection projection : pros) {
	// String nodeID = projection.enode;
	// if (nodeIDSet.contains(nodeID)) {
	// continue;
	// }
	// nodeIDSet.add(nodeID);
	// Integer shardNo = getPreTrajShardNo(nodeID);
	// ArrayList<String> nodeList = resultMap.get(shardNo);
	// if (nodeList == null) {
	// nodeList = new ArrayList<String>();
	// resultMap.put(shardNo, nodeList);
	// }
	// nodeList.add(nodeID);
	// }
	// }
	//
	// return resultMap;
	// }

	/**
	 * 按cell对应的Link集合获取GPS到这些Link集合的投影集合，适合标准的带方位角的浮动车数据
	 * 
	 * @param gps
	 * @param links
	 * @param cellPolygon
	 * @param gpsInterval
	 * @return
	 */
	private ArrayList<Projection> getGpsProjections(GPS gps, ArrayList<Link> links, Polygon cellPolygon, int gpsInterval) {
		// ArrayList<Gps2Projection> prjs = null;
		ArrayList<Projection> pjsArr = new ArrayList<Projection>();
		if (links.size() > 0) {
			for (int i = 0; i < links.size(); i++) {
				Projection gpPrj = null;
				try {
					gpPrj = getGpsProjection(gps, links.get(i), cellPolygon, gpsInterval);
				} catch (Exception e) {
					e.printStackTrace();
					continue;
				}
				//
				if (gpPrj != null) {
					gpPrj.setGps(gps);
					pjsArr.add(gpPrj);
				} else {
					// System.out.println(links.get(i).getId()+" ,return null");
				}
			}
		}

		if (gpsInterval <= averageInterval) {
			// 高频点
			if (pjsArr.size() > projectionNum_HF) {
				adjustProjections(gps, pjsArr, projectionNum_HF);
			}
		} else {
			// 低频点
			if (pjsArr.size() > projectionNum_LF) {
				adjustProjections(gps, pjsArr, projectionNum_LF);
			}
		}

		return pjsArr;
	}

	private void adjustProjections(GPS gps, List<Projection> prjs, int maxNum) {
		double maxCost = -1.0, minCost = Double.MAX_VALUE;
		double maxAng = -1, minAng = 190;
		for (Projection p : prjs) {
			if (p.getCost() > maxCost) {
				maxCost = p.getCost();
			}
			if (p.getCost() < minCost) {
				minCost = p.getCost();
			}

			if (p.getAzimuthDelta() > maxAng) {
				maxAng = p.getAzimuthDelta();
			}
			if (p.getAzimuthDelta() < minAng) {
				minAng = p.getAzimuthDelta();
			}
		}
		final double amin = minCost;
		final double aspan = maxCost - minCost;
		final double bmin = minAng;
		final double bspan = maxAng - minAng;
		// 最多保留maxNum个候选

		Collections.sort(prjs, new Comparator<Projection>() {

			public int compare(Projection o1, Projection o2) {
				// TODO Auto-generated method stub
				double a1 = (o1.getCost() - amin) / aspan;
				// o1.getAzimuthDelta()
				double a2 = (o2.getCost() - amin) / aspan;

				double c1 = (o1.getAzimuthDelta() - bmin) / bspan;
				// o1.getAzimuthDelta()
				double c2 = (o2.getAzimuthDelta() - bmin) / bspan;
				double p1 = ((o1.getPrjDistanceFormSNode() > 0) && (o1.getPrjDistanceFormSNode() < o1.getLinkLenth())) ? 0.5 : 1.0;
				double p2 = ((o2.getPrjDistanceFormSNode() > 0) && (o2.getPrjDistanceFormSNode() < o2.getLinkLenth())) ? 0.5 : 1.0;
				// double dfs1 =
				// Math.abs(o1.getPrjDistanceFormSNode()/o1.getLinkLenth()-0.5)*2;
				// double dfs2 =
				// Math.abs(o2.getPrjDistanceFormSNode()/o2.getLinkLenth()-0.5)*2;
				double dfs1 = Math.abs(p1 - 0.5) * 2;
				double dfs2 = Math.abs(p2 - 0.5) * 2;
				double k1 = 0.4 * a1 + 0.3 * c1 + 0.3 * dfs1;
				double k2 = 0.4 * a2 + 0.3 * c2 + 0.3 * dfs2;
				if (k1 < k2)
					return -1;
				if (k1 > k2)
					return 1;
				return 0;
			}

		});
		// List<Projection> rm = prjs.subList(3, prjs.size());
		// 匹配保留maxNum个，配合去掉方向
		for (int i = prjs.size() - 1; i >= maxNum; i--) {
			prjs.remove(i);
		}
		// prjs.removeAll(rm);
		// int maxCandidateLinks=4;
		// if(prjs.size()>0){
		// //权重排序
		// for(int i=0;i<prjs.size();i++){
		// for(int j=i+1;j<prjs.size();j++){
		// if(prjs.get(i).cost>prjs.get(j).cost){
		// Projection tmpPrj=prjs.get(i);
		// prjs.set(i, prjs.get(j));
		// prjs.set(j, tmpPrj);
		// }
		// }
		// }
		//
		// //double speed=gps.getSpeed();
		// //for(int i=prjs.size()-1;i>-1;i--){//考虑准确率，如果点误差都大，直接跳过更为有利.
		// // for(int
		// i=prjs.size()-1;i>maxCandidateLinks-1;i--){//考虑最大化覆盖率，尽可能保留候选
		// //使用投影距离判断
		// // if(prjs.get(i).prjDistance>50d){
		// // prjs.remove(i);continue;
		// // }
		// //角度差过滤
		// // else
		// if(prjs.get(i).getGps().getDirection()>0&&prjs.get(i).azimuthDelta>30d){
		// // prjs.remove(i);continue;
		// // }
		// //}
		//
		// if(prjs!=null && prjs.size()>maxCandidateLinks-1){
		// for(int i=prjs.size()-1;i>maxCandidateLinks;i--){
		// prjs.remove(i);
		// }
		// }
		// }
	}

	/**
	 * 计算GPS到Link的投影，计算方位角，适合标准带方位角浮动车数据
	 * 
	 * @param gps
	 * @param link
	 * @param cellPolygon
	 * @param gpsInterval
	 * @return
	 * @throws Exception
	 */
	private Projection getGpsProjection(GPS gps, Link link, Polygon cellPolygon, int gpsInterval) throws Exception {
		LineString lineString = link.getGeometry();

		if (!lineString.intersects(cellPolygon)) {
			return null;
		}

		Point point = MapUtil.getPoint(new Coordinate(gps.getLongtitude(), gps.getLatitude()));
		Coordinate cs = MapUtil.closestPoint(point, lineString);

		Point prjp = MapUtil.getPoint(cs);
		//如果gps投影点在link两端则舍弃
		boolean GpsIsAtLinkEnds = judgeGpsIsAtLinkEnds(prjp, lineString);
		
		if(!GpsIsAtLinkEnds)return null;
		
		double prjDistance = MapUtil.calPointDistance(point.getCoordinate(), prjp.getCoordinate());

		Coordinate coordinates[] = lineString.getCoordinates();
		int size = coordinates.length - 1;

		double distance, prjDistanceFormSNode = 0;
		double azimuth = 0;

		int choose = 0;
		for (int i = 0; i < size; i++) {

			distance = MapUtil.calPointDistance(coordinates[i], coordinates[i + 1]);

			LineSegment lineSegment = new LineSegment(coordinates[i], coordinates[i + 1]);
			Coordinate cur = MapUtil.closestPoint2LineSegment(prjp.getCoordinate(), lineSegment);
			if (equal(prjp.getCoordinate(), cur)) {
				distance = MapUtil.calPointDistance(coordinates[i], prjp.getCoordinate());
				prjDistanceFormSNode = prjDistanceFormSNode + distance;
				choose = i;
				break;
			}
			choose = i;
			prjDistanceFormSNode = prjDistanceFormSNode + distance;
		}
		azimuth = MapUtil.azimuth(coordinates[choose], coordinates[choose + 1]);
		// link.setAzimuth(MapUtil.azimuth(coordinates[size-1],
		// coordinates[size]));
		double azimuthDelta = gps.getDirection() - azimuth;

		if (azimuthDelta > 180)
			azimuthDelta = 360 - azimuthDelta;
		else if (azimuthDelta < -180)
			azimuthDelta = 360 + azimuthDelta;

		if (gpsInterval <= averageInterval) {
			// 高频点
			azimuthDelta = Math.abs(azimuthDelta);
			if (azimuthDelta > 90) {
				// System.out.println("gps:"+gps.getDirection()+",zai:"+azimuth);
				return null;
			}
		}

		double cost = 0.0;
		/* 计算link的权值 */
		// if(gps.getDirection()>-1){
		// cost = -this.pointWeighter.computeWeight(gps,azimuthDelta,
		// prjDistance, null);
		// }else{
		cost = prjDistance;
		// }

		Projection projection = new Projection(link.getId(), link.getSnode(), link.getEnode(), link.getLength(), link.getSpeedlimit(), link.getRoadclass(), link.getRoadtype(), prjp.getX(), prjp.getY(), prjDistance, (int) prjDistanceFormSNode, azimuth,
				azimuthDelta, cost);
		return projection;

	}

	private boolean judgeGpsIsAtLinkEnds(Point prjp, LineString lineString) {
		// TODO Auto-generated method stub
		Coordinate coordinates[] = lineString.getCoordinates();
		int size = coordinates.length - 1;

		// 如果投影点是最初和最后一个点，返回false
		if (equal(prjp.getCoordinate(), coordinates[size]) || equal(prjp.getCoordinate(), coordinates[0])) {
			return false;
		}

		return true;
	}

	boolean equal(Coordinate a, Coordinate b) {
		return (Math.abs(a.x - b.x) < 0.0000001) && (Math.abs(a.y - b.y) < 0.0000001);
	}

	/**
	 * 计算GPS到Link的投影，不计算方位角，适合浮动车GPS数据缺少方位角的情况
	 * 
	 * @param gps
	 * @param link
	 * @param cellPolygon
	 * @return
	 */
	private Gps2Projection getGpsProjection2(GPS gps, Link link, Polygon cellPolygon) {

		Point point = MapUtil.getPoint(new Coordinate(gps.getLongtitude(), gps.getLatitude()));
		LineString lineString = link.getGeometry();
		Geometry geo = lineString.intersection(cellPolygon);

		Coordinate cs = MapUtil.closestPoint(point, geo);
		Point prjp = MapUtil.getPoint(cs);

		double prjDistance = MapUtil.calPointDistance(point.getCoordinate(), prjp.getCoordinate());

		Coordinate coordinates[] = lineString.getCoordinates();
		int size = coordinates.length - 1;

		double distance, prjDistanceFormSNode = 0;

		for (int i = 0; i < size; i++) {
			distance = MapUtil.calPointDistance(coordinates[i], coordinates[i + 1]);
			LineSegment lineSegment = new LineSegment(coordinates[i], coordinates[i + 1]);
			if (MapUtil.closestPoint2LineSegment(prjp.getCoordinate(), lineSegment).equals(prjp.getCoordinate())) {
				distance = MapUtil.calPointDistance(coordinates[i], prjp.getCoordinate());
				prjDistanceFormSNode = prjDistanceFormSNode + distance;
				break;
			}
			prjDistanceFormSNode = prjDistanceFormSNode + distance;
		}
		return new Gps2Projection(link.getId(), link.getLength(), link.getSnode(), link.getEnode(), link.getSpeedlimit(), link.getRoadclass(), link.getRoadtype(), prjp, prjDistance, prjDistanceFormSNode);
	}

	private Cell[] readCell(Cell[] cells, int gpsInterval) throws Exception {
		// /*
		// * 整理网格，统一读出网格所包含的路链id
		// */
		// HashMap<String, List<String>> cellIDLinkIDMap =
		// getCellIDLinkIDMap(cells);
		// if (cellIDLinkIDMap == null) {
		// System.out.println("readCell error!");
		// return null;
		// }
		// HashMap<String, Link> linkIDLinkMap =
		// getLinkIDLinkMap(cellIDLinkIDMap
		// .values());

		// 临时变量，用于避免重查询网格link
		HashMap<String, ArrayList<Link>> cellIDLinkListMap = new HashMap<String, ArrayList<Link>>();
		// 临时变量，用于避免重复查询link
		HashMap<String, Link> linkMap = new HashMap<String, Link>();

		for (int i = 0; i < cells.length; i++) {
			Cell cell = cells[i];
			if (!cellIDLinkListMap.containsKey(cell.getCellid())) {
				String[] links = null;
				totalTimes++;
				Position pos = null;
				// pos = cellCacheOper.posMap.get(cell.getCellid());
				if (pos != null) {
					// // long j1 = System.currentTimeMillis();
					// byte[] linkBs = cellCacheOper.getData(pos);
					// links = StringUtils.split(new String(linkBs), COMMA);
					// // long jc1 = System.currentTimeMillis() - j1;
					// // jrCost = jrCost + jc1;
					// jcTimes++;
				} else {
					// long j2 = System.currentTimeMillis();
					List<String> linkIDList = jc.lrange(RouteEstLocal.PRE_CELL + cell.getCellid(), 0, -1);
					// long jc2 = System.currentTimeMillis() - j2;
					// jrCost2 = jrCost2 + jc2;
					// jcTimes2++;
					// System.out.println("cell:" + jc1);
					if (linkIDList.size() == 0) {
						// throw new Exception("Get cell's link failed");
						cell.setCellLinkIDs(new ArrayList<Link>());
						cell.setPrj(getGpsProjections(cell.getPgs(), cell.getCellLinkIDs(), cell.getPolygon(), gpsInterval));
						cellIDLinkListMap.put(cell.getCellid(), new ArrayList<Link>());
						continue;
					}
					links = new String[linkIDList.size()];
					links = linkIDList.toArray(links);
					// if (cellCacheOper.posMap.size() <= cacheCellNum) {
					// // 写入缓存数据
					// // long j1 = System.currentTimeMillis();
					// cellCacheOper.writeData(cell.getCellid(),
					// getCacheData(linkIDList, COMMA));
					// // long jc1 = System.currentTimeMillis() - j1;
					// // jrCost1 = jrCost1 + jc1;
					// jcTimes1++;
					// }
				}
				// 获取link信息
				ArrayList<Link> lnks = new ArrayList<Link>();
				for (String linkID : links) {
					if (linkMap.containsKey(linkID)) {
						lnks.add(linkMap.get(linkID));
						continue;
					}
					linkID = new String(linkID);
					totalTimes++;
					Position lpos = null;
					// lpos = linkCacheOper.posMap.get(linkID);
					if (lpos != null) {
						// long j1 = System.currentTimeMillis();
						// byte[] linkNodeBs = linkCacheOper.getData(lpos);
						// String[] linkNodes = StringUtils.split(new
						// String(linkNodeBs), "\\$");
						// // long jc1 = System.currentTimeMillis() - j1;
						// // jrCost = jrCost + jc1;
						// jcTimes++;
						// try {
						// String snodeid = linkNodes[0];
						// String enodeid = linkNodes[1];
						// int orientation = Integer.parseInt(linkNodes[2]);
						// String roadclass = linkNodes[3];
						// String roadtype = linkNodes[4];
						// int width = Integer.parseInt(linkNodes[5]);
						// int length = Integer.parseInt(linkNodes[6]);
						// int speedLimit = Integer.parseInt(linkNodes[7]);
						// Geometry geometry =
						// MapUtil.parseWktString(linkNodes[8]);
						// LineString ln = (LineString) geometry;
						//
						// Link n = new Link(linkID, snodeid, enodeid,
						// orientation, roadclass, roadtype, width, length,
						// speedLimit, ln);
						// lnks.add(n);
						// linkMap.put(linkID, n);
						// } catch (Exception e) {
						// // continue;
						// }
						// continue;
					}
					// long j2 = System.currentTimeMillis();
					String key = RouteEstLocal.PRE_LINK + linkID;
					List<String> linkInfo = this.jc.hmget(key, "snodeid", "enodeid", "orientation", "roadclass", "roadtype", "width", "length", "speedLimit", "ln");
					// long jc2 = System.currentTimeMillis() - j2;
					// jrCost2 = jrCost2 + jc2;
					// jcTimes2++;
					try {
						String snodeid = linkInfo.get(0);
						String enodeid = linkInfo.get(1);
						int orientation = Integer.parseInt(linkInfo.get(2));
						String roadclass = linkInfo.get(3);
						String roadtype = linkInfo.get(4);
						int width = Integer.parseInt(linkInfo.get(5));
						int length = Integer.parseInt(linkInfo.get(6));
						int speedLimit = Integer.parseInt(linkInfo.get(7));
						Geometry geometry = MapUtil.parseWktString(linkInfo.get(8));
						LineString ln = (LineString) geometry;

						Link n = new Link(linkID, snodeid, enodeid, orientation, roadclass, roadtype, width, length, speedLimit, ln);
						lnks.add(n);
						linkMap.put(linkID, n);
						// if (cellCacheOper.posMap.size() <= cacheCellNum) {
						// // 写入缓存数据
						// // long j1 = System.currentTimeMillis();
						// linkCacheOper.writeData(linkID,
						// getCacheData(linkInfo, SEPERA));
						// // long jc1 = System.currentTimeMillis() - j1;
						// // jrCost1 = jrCost1 + jc1;
						// jcTimes1++;
						// }
					} catch (Exception e) {
						continue;
					}
				}
				cellIDLinkListMap.put(cell.getCellid(), lnks);
			}

			cell.setCellLinkIDs(cellIDLinkListMap.get(cell.getCellid()));
			cell.setPrj(getGpsProjections(cell.getPgs(), cell.getCellLinkIDs(), cell.getPolygon(), gpsInterval));
		}

		// 清空缓存
		cellIDLinkListMap.clear();
		linkMap.clear();

		return cells;
	}

	public String printTimeCost() {
		return jrCost + "|" + jcTimes + "," + jrCost1 + "|" + jcTimes1 + "," + jrCost2 + "|" + jcTimes2 + "," + rdCost + "|" + totalTimes;
	}

	public String printTimes() {
		return jcTimes + "," + jcTimes1 + "," + totalTimes + "," + rdCost;
	}

	private byte[] getCacheData(List<String> linkIDList, String sepera) {
		StringBuffer sb = new StringBuffer();
		for (String link : linkIDList) {
			sb.append(link).append(sepera);
		}
		sb.deleteCharAt(sb.length() - 1);

		return sb.toString().getBytes();
	}

	private byte[] getCacheData(HashMap<String, String> snodeMap) {
		StringBuffer sb = new StringBuffer();
		Iterator<Entry<String, String>> it = snodeMap.entrySet().iterator();
		while (it.hasNext()) {
			Entry<String, String> entry = it.next();
			sb.append(entry.getKey()).append(SEPERB).append(entry.getValue()).append(SEPERA);
		}
		sb.deleteCharAt(sb.length() - 1);

		return sb.toString().getBytes();
	}

	/**
	 * TODO(功能描述)
	 * 
	 * @param values
	 * @return
	 */
	private HashMap<String, Link> getLinkIDLinkMap(Collection<List<String>> values) {
		HashMap<String, Link> resultMap = new HashMap<String, Link>();
		for (List<String> links : values) {
			for (String linkID : links) {
				if (resultMap.containsKey(linkID)) {
					continue;
				}
				String key = RouteEstLocal.PRE_LINK + linkID;
				List<String> linkInfo = this.jc.hmget(key, "snodeid", "enodeid", "orientation", "roadclass", "roadtype", "width", "length", "speedLimit", "ln");
				try {
					String snodeid = linkInfo.get(0);
					String enodeid = linkInfo.get(1);
					int orientation = Integer.parseInt(linkInfo.get(2));
					String roadclass = linkInfo.get(3);
					String roadtype = linkInfo.get(4);
					int width = Integer.parseInt(linkInfo.get(5));
					int length = Integer.parseInt(linkInfo.get(6));
					int speedLimit = Integer.parseInt(linkInfo.get(7));
					Geometry geometry = MapUtil.parseWktString(linkInfo.get(8));
					LineString ln = (LineString) geometry;

					Link n = new Link(linkID, snodeid, enodeid, orientation, roadclass, roadtype, width, length, speedLimit, ln);
					resultMap.put(linkID, n);
				} catch (Exception e) {
					continue;
				}
			}
		}
		return resultMap;
	}

	/**
	 * TODO(功能描述)
	 * 
	 * @param cells
	 * @return
	 */
	private HashMap<String, List<String>> getCellIDLinkIDMap(Cell[] cells) {
		// TODO Auto-generated method stub
		HashMap<String, List<String>> cellIDLinkIDListMap = new HashMap<String, List<String>>();
		for (Cell cell : cells) {
			if (cellIDLinkIDListMap.containsKey(cell.getCellid())) {
				continue;
			}
			List<String> linkIDList = jc.lrange(RouteEstLocal.PRE_CELL + cell.getCellid(), 0, -1);
			HashSet<String> idSet = new HashSet<String>();
			for (String linkID : linkIDList) {
				idSet.add(linkID);
			}
			if (linkIDList != null) {
				cellIDLinkIDListMap.put(cell.getCellid(), new ArrayList<String>(idSet));
			}
		}
		return cellIDLinkIDListMap;
	}

	/**
	 * TODO(功能描述)
	 * 
	 * @param shardNoLinkIDMap
	 * @return
	 */
	// private HashMap<String, Link> getLinkIDLinkMap(
	// HashMap<Integer, ArrayList<String>> shardNoLinkIDMap) {
	// // TODO Auto-generated method stub
	// HashMap<String, Link> resultMap = new HashMap<String, Link>();
	//
	// // 并行读取link信息
	// int threadCount = shardNoLinkIDMap.keySet().size();
	// CountDownLatch rlatch = new CountDownLatch(threadCount);
	// for (Integer shardNo : shardNoLinkIDMap.keySet()) {
	// RedisReaderThread thread = shardingReaderThreadMap.get(shardNo);
	// if (thread == null) {
	// thread = new RedisReaderThread(shardNo);
	// shardingReaderThreadMap.put(shardNo, thread);
	// }
	// thread.setCountDownLatch(rlatch);
	// thread.setReadFlag(CNConfig.READ_LINK);
	// thread.setLinkIDArray(shardNoLinkIDMap.get(shardNo));
	// new Thread(thread).start();
	// }
	// try {
	// rlatch.await();
	// } catch (InterruptedException e1) {
	// // TODO Auto-generated catch block
	// System.out.println("rlatch.await() error!");
	// return null;
	// }
	// for (Integer shardNo : shardNoLinkIDMap.keySet()) {
	// RedisReaderThread thread = shardingReaderThreadMap.get(shardNo);
	// resultMap.putAll(thread.getLinkIDInfoMap());
	// thread.clear();
	// }
	//
	// /*
	// * for (Integer shardNo : shardNoLinkIDMap.keySet()) { RedisMasterSlave
	// * rms = shardingConfigMap.get(shardNo); // 得到分片的所有主-从节点
	// * ArrayList<String> urls = getUrls(rms); if (urls == null) {
	// * System.out.println("cannot find instance save shard:" + shardNo);
	// * return null; } for (String url : urls) { JedisMapPool pool =
	// * redisPoolMap.get(url); if (pool == null) { pool = new
	// * JedisMapPool(url); redisPoolMap.put(url, pool); } Jedis jedis = null;
	// * try { jedis = pool.getJedis(); if (jedis != null) { Pipeline pl =
	// * jedis.pipelined();
	// *
	// * ArrayList<String> linkIDs = shardNoLinkIDMap.get(shardNo); for
	// * (String linkID : linkIDs) { String key = PRE_LINK + linkID;
	// * pl.hmget(key, "snodeid", "enodeid", "orientation", "roadclass",
	// * "roadtype", "width", "length", "speedLimit", "ln"); } List<Object>
	// * linkInfoList = pl.syncAndReturnAll();
	// *
	// * for (int i = 0;i < linkInfoList.size();i++) { List<String> linkInfo =
	// * (List<String>)linkInfoList.get(i);
	// *
	// * String snodeid = linkInfo.get(0); String enodeid = linkInfo.get(1);
	// * int orientation = Integer.parseInt(linkInfo.get(2)); String roadclass
	// * = linkInfo.get(3); String roadtype = linkInfo.get(4); int width =
	// * Integer.parseInt(linkInfo.get(5)); int length =
	// * Integer.parseInt(linkInfo.get(6)); int speedLimit =
	// * Integer.parseInt(linkInfo.get(7)); Geometry geometry =
	// * MapUtil.parseWktString(linkInfo.get(8)); LineString ln =
	// * (LineString)geometry;
	// *
	// * Link n = new Link(linkIDs.get(i), snodeid, enodeid , orientation,
	// * roadclass, roadtype, width, length, speedLimit, ln);
	// * resultMap.put(linkIDs.get(i), n); }
	// *
	// * } else { System.out.println("cannot not get jedis:" + url); continue;
	// * } } catch (Exception e) {
	// * System.out.println("get cell from redis error:" + url); continue; }
	// * finally { if (jedis != null) { pool.releaseJedis(jedis); } } break; }
	// * }
	// */
	// return resultMap;
	// }

	/**
	 * TODO(功能描述)
	 * 
	 * @param cellIDLinkIDMap
	 * @return
	 */
	// private HashMap<Integer, ArrayList<String>> getShardNoLinkIDMap(
	// HashMap<String, List<String>> cellIDLinkIDMap) {
	// // TODO Auto-generated method stub
	// HashMap<Integer, ArrayList<String>> resultMap = new HashMap<Integer,
	// ArrayList<String>>();
	// HashSet<String> linkIDSet = new HashSet<String>();
	// for (List<String> linkIDs : cellIDLinkIDMap.values()) {
	// for (String linkID : linkIDs) {
	// if (linkIDSet.contains(linkID)) {
	// continue;
	// }
	// linkIDSet.add(linkID);
	//
	// Integer shardNo = Math.abs(Integer.parseInt(linkID))
	// % shardingConfigMap.size();
	// if (resultMap.containsKey(shardNo)) {
	// resultMap.get(shardNo).add(linkID);
	// } else {
	// ArrayList<String> linkIDList = new ArrayList<String>();
	// linkIDList.add(linkID);
	// resultMap.put(shardNo, linkIDList);
	// }
	// }
	// }
	// return resultMap;
	// }

	/**
	 * TODO(功能描述)
	 * 
	 * @param shardNoCellIDMap
	 * @return
	 */
	// private HashMap<String, List<String>> getCellIDLinkIDMap(
	// HashMap<Integer, ArrayList<String>> shardNoCellIDMap) {
	// // TODO Auto-generated method stub
	// HashMap<String, List<String>> resultMap = new HashMap<String,
	// List<String>>();
	//
	// // 并行读取网格包含的link序列
	// int threadCount = shardNoCellIDMap.keySet().size();
	// CountDownLatch rlatch = new CountDownLatch(threadCount);
	// for (Integer shardNo : shardNoCellIDMap.keySet()) {
	// RedisReaderThread thread = shardingReaderThreadMap.get(shardNo);
	// if (thread == null) {
	// thread = new RedisReaderThread(shardNo);
	// shardingReaderThreadMap.put(shardNo, thread);
	// }
	// thread.setCountDownLatch(rlatch);
	// thread.setReadFlag(CNConfig.READ_CELL);
	// thread.setCellIDArray(shardNoCellIDMap.get(shardNo));
	// new Thread(thread).start();
	// }
	// try {
	// rlatch.await();
	// } catch (InterruptedException e1) {
	// // TODO Auto-generated catch block
	// System.out.println("rlatch.await() error!");
	// return null;
	// }
	// for (Integer shardNo : shardNoCellIDMap.keySet()) {
	// RedisReaderThread thread = shardingReaderThreadMap.get(shardNo);
	// resultMap.putAll(thread.getCellIDLinkIDListMap());
	// thread.clear();
	// }
	//
	// /*
	// * for (Integer shardNo : shardNoCellIDMap.keySet()) { RedisMasterSlave
	// * rms = shardingConfigMap.get(shardNo); // 得到分片的所有主-从节点
	// * ArrayList<String> urls = getUrls(rms); if (urls == null) {
	// * System.out.println("cannot find instance save shard:" + shardNo);
	// * return null; } for (String url : urls) { JedisMapPool pool =
	// * redisPoolMap.get(url); if (pool == null) { pool = new
	// * JedisMapPool(url); redisPoolMap.put(url, pool); } Jedis jedis = null;
	// * try { jedis = pool.getJedis(); if (jedis != null) { Pipeline pl =
	// * jedis.pipelined(); ArrayList<String> cellIDs =
	// * shardNoCellIDMap.get(shardNo); for (String cellID : cellIDs) {
	// * pl.lrange(PRE_CELL + cellID, 0, -1); } List<Object> linkIDs =
	// * pl.syncAndReturnAll(); for (int i = 0;i < linkIDs.size();i++) { //
	// * Response<List<String>> linkIDList =
	// * (Response<List<String>>)linkIDs.get(i); List<String> linkIDList =
	// * (List<String>)linkIDs.get(i); resultMap.put(cellIDs.get(i),
	// * linkIDList); } // List<String> linkIDs = jedis.lrange(PRE_CELL +
	// * cellID, 0, -1); // if (linkIDs != null) { // String[] returnData =
	// * new String[linkIDs.size()]; // for (int i = 0;i <
	// * returnData.length;i++) { // returnData[i] = linkIDs.get(i); // } //
	// * return returnData; // } else { //
	// * System.out.println("0 links in cell:" + cellID); // } } else {
	// * System.out.println("cannot not get jedis:" + url); continue; } }
	// * catch (Exception e) { System.out.println("get cell from redis error:"
	// * + url); continue; } finally { if (jedis != null) {
	// * pool.releaseJedis(jedis); } } break; } }
	// */
	// return resultMap;
	// }

	/**
	 * TODO(功能描述)
	 * 
	 * @param cells
	 * @return
	 */
	// private HashMap<Integer, ArrayList<String>> getShardNoCellIDMap(Cell[]
	// cells) {
	// // TODO Auto-generated method stub
	// HashMap<Integer, ArrayList<String>> resultMap = new HashMap<Integer,
	// ArrayList<String>>();
	// HashSet<String> cellIDSet = new HashSet<String>();
	// for (Cell cell : cells) {
	// String cellID = cell.getCellid();
	// if (cellIDSet.contains(cellID)) {
	// continue;
	// }
	// cellIDSet.add(cellID);
	//
	// Integer shardNo = getCellShardNo(cellID);
	// if (resultMap.containsKey(shardNo)) {
	// resultMap.get(shardNo).add(cellID);
	// } else {
	// ArrayList<String> cellIDList = new ArrayList<String>();
	// cellIDList.add(cellID);
	// resultMap.put(shardNo, cellIDList);
	// }
	// }
	// return resultMap;
	// }

	/**
	 * TODO(功能描述)
	 * 
	 * @param cellid
	 * @return
	 */
	// private String[] readCellInfoFromRedis(String cellID) {
	// // TODO Auto-generated method stub
	// Integer shardingNo = getCellShardNo(cellID);
	// RedisMasterSlave rms = shardingConfigMap.get(shardingNo);
	// // 得到分片的所有主-从节点
	// ArrayList<String> urls = getUrls(rms);
	// if (urls == null) {
	// System.out.println("cannot find instance save shard:" + shardingNo);
	// return null;
	// }
	// for (String url : urls) {
	// JedisMapPool pool = redisPoolMap.get(url);
	// if (pool == null) {
	// pool = new JedisMapPool(url);
	// redisPoolMap.put(url, pool);
	// }
	// Jedis jedis = null;
	// try {
	// jedis = pool.getJedis();
	// if (jedis != null) {
	// List<String> linkIDs = jedis.lrange(PRE_CELL + cellID, 0,
	// -1);
	// if (linkIDs != null) {
	// String[] returnData = new String[linkIDs.size()];
	// for (int i = 0; i < returnData.length; i++) {
	// returnData[i] = linkIDs.get(i);
	// }
	// return returnData;
	// } else {
	// System.out.println("0 links in cell:" + cellID);
	// }
	// } else {
	// System.out.println("cannot not get jedis:" + url);
	// }
	// } catch (Exception e) {
	// System.out.println("get cell from redis error:" + url);
	// } finally {
	// if (jedis != null) {
	// pool.releaseJedis(jedis);
	// }
	// }
	// }
	//
	// return null;
	// }

	/**
	 * TODO(功能描述)
	 * 
	 * @param rms
	 * @return
	 */
	private ArrayList<String> getUrls(RedisMasterSlave rms) {
		// TODO Auto-generated method stub
		if (rms == null)
			return null;
		ArrayList<String> urls = new ArrayList<String>();
		urls.add(rms.masterUrl);
		urls.addAll(rms.slaveUrl);
		return urls;
	}

	/**
	 * TODO(功能描述)
	 * 
	 * @param cellid
	 * @return
	 */
	// private Integer getCellShardNo(String cellID) {
	// // TODO Auto-generated method stub
	// String[] tmp = cellID.split("_");
	// Integer meshID = Integer.parseInt(tmp[0]);
	// return meshID / 100 % shardingConfigMap.size();
	// }

	// private ArrayList<Link> readLinks(String[] links,
	// HashMap<String, Link> cache) throws Exception {
	// // String ids = "";
	// ArrayList<Link> lst = new ArrayList<Link>();
	//
	// for (int i = 0; i < links.length; i++) {
	// if (cache.containsKey(links[i])) {
	// lst.add(cache.get(links[i]));
	// continue;
	// }
	//
	// Link n = readLinkFromRedis(links[i]);
	// if (n == null) {
	// System.out.println("readLinkFromRedis error!");
	// continue;
	// }
	// cache.put(links[i], n);
	// lst.add(n);
	// }
	//
	// return lst;
	// }

	/**
	 * TODO(功能描述)
	 * 
	 * @param string
	 * @return
	 */
	// private Link readLinkFromRedis(String linkID) {
	// // TODO Auto-generated method stub
	// Integer shardingNo = Math.abs(Integer.parseInt(linkID))
	// % shardingConfigMap.size();
	// RedisMasterSlave rms = shardingConfigMap.get(shardingNo);
	// // 得到分片的所有主-从节点
	// ArrayList<String> urls = getUrls(rms);
	// if (urls == null) {
	// System.out.println("cannot find instance save shard:" + shardingNo);
	// return null;
	// }
	// for (String url : urls) {
	// JedisMapPool pool = redisPoolMap.get(url);
	// if (pool == null) {
	// pool = new JedisMapPool(url);
	// redisPoolMap.put(url, pool);
	// }
	// Jedis jedis = null;
	// try {
	// jedis = pool.getJedis();
	// if (jedis != null) {
	// String key = PRE_LINK + linkID;
	// List<String> linkInfo = jedis.hmget(key, "snodeid",
	// "enodeid", "orientation", "roadclass", "roadtype",
	// "width", "length", "speedLimit", "ln");
	// //
	// // Map<String, String> linkInfo = jedis.hgetAll(key);
	// String snodeid = linkInfo.get(0);
	// String enodeid = linkInfo.get(1);
	// int orientation = Integer.parseInt(linkInfo.get(2));
	// String roadclass = linkInfo.get(3);
	// String roadtype = linkInfo.get(4);
	// int width = Integer.parseInt(linkInfo.get(5));
	// int length = Integer.parseInt(linkInfo.get(6));
	// int speedLimit = Integer.parseInt(linkInfo.get(7));
	// Geometry geometry = MapUtil.parseWktString(linkInfo.get(8));
	// LineString ln = (LineString) geometry;
	//
	// // String snodeid = jedis.hget(key, "snodeid");
	// // String enodeid = jedis.hget(key, "enodeid");
	// // int orientation = Integer.parseInt(jedis.hget(key,
	// // "orientation"));
	// // String roadclass = jedis.hget(key, "roadclass");
	// // String roadtype = jedis.hget(key, "roadtype");
	// // int width = Integer.parseInt(jedis.hget(key, "width"));
	// // int length = Integer.parseInt(jedis.hget(key, "length"));
	// // int speedLimit = Integer.parseInt(jedis.hget(key,
	// // "speedLimit"));
	// //
	// // Geometry geometry =
	// // MapUtil.parseWktString(jedis.hget(key, "ln"));
	// // LineString ln = (LineString)geometry;
	//
	// Link n = new Link(linkID, snodeid, enodeid, orientation,
	// roadclass, roadtype, width, length, speedLimit, ln);
	// return n;
	// } else {
	// System.out.println("cannot not get jedis:" + url);
	// }
	// } catch (NumberFormatException e) {
	// System.out.println("NumberFormat error!");
	// } catch (Exception e) {
	// System.out.println("get link from redis error:" + url);
	// } finally {
	// if (jedis != null) {
	// pool.releaseJedis(jedis);
	// }
	// }
	// }
	// return null;
	// }

	private Neo4JPath readLinks(String link, HashMap<String, Link> linkIDLinkMap) throws Exception {
		String[] links = StringUtils.split(link, ";");

		CaPathLink[] tt = new CaPathLink[links.length];
		int cost = 0;
		for (int i = 0; i < links.length; i++) {
			String[] s = StringUtils.split(links[i], ",");
			String id = new String(s[0]);
			Link linkInfo = linkIDLinkMap.get(id);

			if (linkInfo == null) {
				linkInfo = readLink(id);
				if (linkInfo == null) {
					return new Neo4JPath(0, null);
				}
				linkIDLinkMap.put(id, linkInfo);
			}

			int orientation = linkInfo.direction;
			String roadclass = linkInfo.roadclass;
			String roadtype = linkInfo.roadtype;

			int width = (int) linkInfo.width;
			int length = (int) linkInfo.length;
			cost += length;
			int speedLimit = linkInfo.speedlimit;

			double azimuth = linkInfo.azimuth;

			CaPathLink caLink = new CaPathLink(id, width, length, speedLimit, orientation, roadtype, roadclass, azimuth);

			tt[i] = caLink;
		}
		List<CaPathLink> lst = Arrays.asList(tt);
		return new Neo4JPath(cost, lst);
	}

	/**
	 * TODO(功能描述)
	 * 
	 * @param id
	 * @return
	 */
	private Link readLink(String linkID) {
		// TODO Auto-generated method stub
		String key = RouteEstLocal.PRE_LINK + linkID;
		List<String> linkInfo = this.jc.hmget(key, "snodeid", "enodeid", "orientation", "roadclass", "roadtype", "width", "length", "speedLimit", "ln");
		try {
			String snodeid = linkInfo.get(0);
			String enodeid = linkInfo.get(1);
			int orientation = Integer.parseInt(linkInfo.get(2));
			String roadclass = linkInfo.get(3);
			String roadtype = linkInfo.get(4);
			int width = Integer.parseInt(linkInfo.get(5));
			int length = Integer.parseInt(linkInfo.get(6));
			int speedLimit = Integer.parseInt(linkInfo.get(7));
			Geometry geometry = MapUtil.parseWktString(linkInfo.get(8));
			LineString ln = (LineString) geometry;

			Link n = new Link(linkID, snodeid, enodeid, orientation, roadclass, roadtype, width, length, speedLimit, ln);
			return n;
		} catch (Exception e) {
			return null;
		}
	}

	/**
	 * 
	 * @param neo4JPaths
	 * @param startprojectionArr
	 * @param endProjectionArr
	 * @param linkIDLinkMap
	 * @return
	 */
	public ArrayList<CaPath> getCaPaths(Projection[] startprojectionArr, Projection[] endProjectionArr, HashMap<String, Link> linkIDLinkMap) {
		ArrayList<CaPath> paths = null;
		if (startprojectionArr != null && endProjectionArr != null && startprojectionArr.length > 0 && endProjectionArr.length > 0) {
			try {
				ArrayList<String> sids = new ArrayList<String>();
				ArrayList<Projection> sidsP = new ArrayList<Projection>();
				ArrayList<String> eids = new ArrayList<String>();
				ArrayList<Projection> eidsP = new ArrayList<Projection>();
				paths = new ArrayList<CaPath>();

				for (int i = 0; i < startprojectionArr.length; i++) {
					for (int j = 0; j < endProjectionArr.length; j++) {

						// //测试
						// if (startprojectionArr[i].linkID.equals("43080")) {
						// System.out.println(endProjectionArr[i].linkID);
						// }

						if ((!startprojectionArr[i].linkID.equalsIgnoreCase(endProjectionArr[j].linkID)) && (!startprojectionArr[i].enode.equalsIgnoreCase(endProjectionArr[j].snode))) {
							sids.add(startprojectionArr[i].enode);
							sidsP.add(startprojectionArr[i]);

							eids.add(endProjectionArr[j].snode);
							eidsP.add(endProjectionArr[j]);
						} else {
							CaPath path = new CaPath(startprojectionArr[i], endProjectionArr[j], null, 0);
							// paths.add(path);
							if (!filterCaPath(path)) {
								paths.add(path);
							}
							// else{
							// System.out.println("flter");
							// }
						}
					}
				}

				List<Neo4JPath> neo4JPaths = this.getNeo4JPaths(sids, eids, linkIDLinkMap);
				// long t2 = System.currentTimeMillis();
				// System.out.println("------------");
				if (neo4JPaths != null) {
					for (int i = 0; i < neo4JPaths.size(); i++) {
						Neo4JPath neoPath = neo4JPaths.get(i);
						if (neoPath != null && neoPath.getLinks() != null && neoPath.getLinks().size() > 0) {
							// ArrayList<CaPathLink> caLinks = new
							// ArrayList<CaPathLink>();

							// for (int j = 0; j < neoPath.getLinks().size();
							// j++) {
							// Neo4JLink neo4jLink = neoPath.getLinks().get(j);
							//
							// String id = neo4jLink.getId();
							// double width = neo4jLink.getWidth();
							// double length = neo4jLink.getLength();
							// double speedlimit = neo4jLink.getSpeedlimit();
							// int direction = neo4jLink.getDirection();
							// String kind = neo4jLink.getKind();
							// String roadclass = neo4jLink.getRoadlass();
							//
							// CaPathLink caLink = new CaPathLink(id, width,
							// length, speedlimit, direction, kind,
							// roadclass);
							// caLink.setsNodeid(neo4jLink.getsNodeid());
							// caLink.seteNodeid(neo4jLink.geteNodeid());
							// caLinks.add(caLink);
							// }

							double pathLength = neoPath.getCost();
							CaPath path = new CaPath(sidsP.get(i), eidsP.get(i), new ArrayList<CaPathLink>(neoPath.getLinks()), pathLength);
							if (!filterCaPath(path)) {
								paths.add(path);
							}
							// else{
							// System.out.println("flter");
							// }
						}
					}
				}

				// //临时，高频点无预处理前临时采用
				// IPathWeightModel pathWeighter = new
				// PathWeightModelShortest();
				// // 计算权重
				// for (int i = 0; i < paths.size(); i++) {
				// CaPath path = paths.get(i);
				//
				// double cost =
				// pathWeighter.computeWeight(path.getSt().getGps(),
				// path.getEd().getGps(), path, null);
				// path.setCost(cost);
				// }

			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		return paths;
	}

	/*
	 * 平均速度超过任何一个link的限速，则该条path舍弃
	 */
	boolean filterCaPath(CaPath p) {
		double len = p.getPathsLength();// +clen+p.getEd().prjDistanceFormSNode;
		long t = (p.getEd().getGps().getTime() - p.getSt().gps.getTime());
		if (t == 0) {
			t = 1;
		}
		double speed = (len / t) * 3.6;

		if (speed < 0) {
			return true;
		}

		if (p.st.speedlimit >= RouteEstLocal.speedLimit) {
			if (speed > p.st.speedlimit * RouteEstLocal.speedFactor_HS) {
				return true;
			}
		} else {
			if (speed > p.st.speedlimit * RouteEstLocal.speedFactor_LS) {
				return true;
			}
		}

		if (p.getPaths() != null) {
			for (CaPathLink calink : p.getPaths()) {
				if (calink.speedlimit >= RouteEstLocal.speedLimit) {
					if (speed > calink.speedlimit * RouteEstLocal.speedFactor_HS) {
						return true;
					}
				} else {
					if (speed > calink.speedlimit * RouteEstLocal.speedFactor_LS) {
						return true;
					}
				}
			}
		}
		if (p.ed.speedlimit >= RouteEstLocal.speedLimit) {
			if (speed > p.ed.speedlimit * RouteEstLocal.speedFactor_HS) {
				return true;
			}
		} else {
			if (speed > p.ed.speedlimit * RouteEstLocal.speedFactor_LS) {
				return true;
			}
		}

		return false;
	}

	/**
	 * 
	 * @param sNodeIDs
	 * @param eNodeIDs
	 * @param linkIDLinkMap
	 * @return
	 * @throws Exception
	 * @throws TException
	 */
	private List<Neo4JPath> getNeo4JPaths(List<String> sNodeIDs, List<String> eNodeIDs, HashMap<String, Link> linkIDLinkMap) throws Exception {
		// this.count.put("getNeo4JPaths", count.get("getNeo4JPaths") + 1);
		// long t1 = new Date().getTime();
		// 处理重复计算的问题
		ArrayList<String> seq2Ids = new ArrayList<String>();
		HashMap<String, String> id2cmp = new HashMap<String, String>();

		for (int i = 0; i < sNodeIDs.size(); i++) {
			seq2Ids.add(sNodeIDs.get(i) + "_" + eNodeIDs.get(i));
			id2cmp.put(sNodeIDs.get(i) + "_" + eNodeIDs.get(i), sNodeIDs.get(i) + "_" + eNodeIDs.get(i));
		}
		// 参与计算的ID
		ArrayList<String> sids = new ArrayList<String>();
		ArrayList<String> eids = new ArrayList<String>();

		Iterator<Entry<String, String>> iterator = id2cmp.entrySet().iterator();
		while (iterator.hasNext()) {
			Entry<String, String> entry = iterator.next();
			String s[] = StringUtils.split(entry.getValue(), "_");
			sids.add(new String(s[0]));
			eids.add(new String(s[1]));
		}
		// System.out.println("sid:" + sids + " eids:" + eids);
		// List<WeightedPath> wpaths = astar.find(sids, eids);
		// System.out.println("s size="+sids.size()+" ,e size="+eids.size());
		// long t1 = System.currentTimeMillis();
		// System.out.println("start find!");
		List<String> wpaths = find(sids, eids);
		// System.out.println("end find!");
		// long t2 = System.currentTimeMillis();

		// ID队列还原
		HashMap<String, String> n2path = new HashMap<String, String>();
		for (int i = 0; i < wpaths.size(); i++) {
			n2path.put(sids.get(i) + "_" + eids.get(i), wpaths.get(i));
		}
		ArrayList<Neo4JPath> paths = new ArrayList<Neo4JPath>();
		for (int i = 0; i < seq2Ids.size(); i++) {
			String path = n2path.get(seq2Ids.get(i));
			if (path != null) {
				paths.add(readLinks(path, linkIDLinkMap));
			} else {
				paths.add(new Neo4JPath(0, null));
			}
		}
		// long t3 = System.currentTimeMillis();
		// System.out.println("rt="+(t2-t1)+",links="+(t3-t2));
		// long t2 = new Date().getTime();
		// time.put("getNeo4JPaths", time.get("getNeo4JPaths") + (t2 - t1));
		return paths;
	}

	List<String> find(ArrayList<String> s, ArrayList<String> e) throws IOException {
		// BooleanQuery query = new BooleanQuery();
		ArrayList<String> lst = new ArrayList<String>();
		/*
		 * HashMap<String,HashMap<String, String>> trajBuffer = new
		 * HashMap<String,HashMap<String, String>>(); HashMap<Integer,
		 * ArrayList<String>> shardNoSnodeMap = getShardNoSnodeMap(s);
		 * 
		 * //并行读取网格包含的link序列 int threadCount = shardNoSnodeMap.keySet().size();
		 * CountDownLatch rlatch = new CountDownLatch(threadCount); for (Integer
		 * shardNo : shardNoSnodeMap.keySet()) { RedisReaderThread thread =
		 * shardingReaderThreadMap.get(shardNo); if (thread == null) { thread =
		 * new RedisReaderThread(shardNo); shardingReaderThreadMap.put(shardNo,
		 * thread); } thread.setCountDownLatch(rlatch);
		 * thread.setReadFlag(CNConfig.READ_PRETRAJ);
		 * thread.setSnodeIDArray(shardNoSnodeMap.get(shardNo)); new
		 * Thread(thread).start(); } try { rlatch.await(); } catch
		 * (InterruptedException e1) { // TODO Auto-generated catch block
		 * System.out.println("rlatch.await() error!"); return null; } for
		 * (Integer shardNo : shardNoSnodeMap.keySet()) { RedisReaderThread
		 * thread = shardingReaderThreadMap.get(shardNo);
		 * trajBuffer.putAll(thread.getSnodePreTrajMap()); thread.clear(); }
		 */

		for (int i = 0; i < s.size(); i++) {
			String id = s.get(i);
			// 保存轨迹信息
			String trajectoryInfo = null;
			// 保存两点间的路链信息，由于路径查找是从最后一条路链反向找到的一条路链，因此用栈结构保存
			Stack<String> linkInfoBuffer = new Stack<String>();

			String lastLinkInfo = null;
			// HashMap<String, String> trajMap = trajBuffer.get(id);
			HashMap<String, String> trajMap = this.snodePreTrajMap.get(id);
			if (trajMap != null) {
				lastLinkInfo = trajMap.get(e.get(i));
			} else {
				lst.add(null);
				continue;
			}
			if (lastLinkInfo == null) {
				// System.out
				// .println("cannot get linkInfo:" + id + "," + e.get(i));
				lst.add(null);
				continue;
			}
			String[] info = StringUtils.split(lastLinkInfo, ",");
			if (info.length != 3) {
				// System.out.println("get linkinfo error!" + lastLinkInfo);
				lst.add(null);
				continue;
			}
			linkInfoBuffer.push(lastLinkInfo);
			String preNodeID = new String(info[2]);

			// 如果没有找到起点，则继续往前查找，路链信息入栈
			HashSet<String> tmpNodes = new HashSet<String>();
			tmpNodes.add(preNodeID);
			while (!preNodeID.equals(id)) {
				lastLinkInfo = trajMap.get(preNodeID);
				// lastLinkInfo = jedis.hget(key, preNodeID);
				// System.out.println("Find get while lastLinkInfo!");
				if (lastLinkInfo == null) {
					// System.out.println("preTraj error:" + id + "," +
					// preNodeID);
					linkInfoBuffer.clear();
					break;
				}
				String[] tmp = StringUtils.split(lastLinkInfo, ",");
				if (tmp.length != 3) {
					// System.out.println("preTraj error:" + id + "," +
					// preNodeID);
					linkInfoBuffer.clear();
					break;
				}
				linkInfoBuffer.push(lastLinkInfo);
				preNodeID = new String(tmp[2]);
				if (tmpNodes.contains(preNodeID)) {
					linkInfoBuffer.clear();
					// System.out.println("Error preTraj:" + id + "," +
					// info[2]);
					break;
				}
				tmpNodes.add(preNodeID);
				// System.out.println("Find get preNodeID!");
			}
			tmpNodes.clear();
			// 如果当前link的前一个点为起点，则找到了路径，linkInfoBuffer出栈，保存轨迹
			// 轨迹格式为：linkID,length,snodeID;linkID,length,snodeID;
			trajectoryInfo = getTrajectory(linkInfoBuffer);
			linkInfoBuffer.clear();
			// 不过两点间路径是否找到，都要保存，无路径为null
			lst.add(trajectoryInfo);
		}

		/*
		 * for (int i = 0; i < s.size(); i++) { String id = s.get(i); //
		 * if(id.equalsIgnoreCase
		 * ("500499")&&e.get(i).equalsIgnoreCase("501028")){ //
		 * System.out.println(""); // } //保存轨迹信息 String trajectoryInfo = null;
		 * //保存两点间的路链信息，由于路径查找是从最后一条路链反向找到的一条路链，因此用栈结构保存 Stack<String>
		 * linkInfoBuffer = new Stack<String>(); //根据snodeid计算分片 Integer
		 * shardingNo = getPreTrajShardNo(id); RedisMasterSlave rms =
		 * shardingConfigMap.get(shardingNo); // 得到分片的所有主-从节点 ArrayList<String>
		 * urls = getUrls(rms); if (urls == null) { System.out.println(
		 * "cannot find instance save shard:" + shardingNo); return null; } for
		 * (String url : urls) { JedisMapPool pool = redisPoolMap.get(url); if
		 * (pool == null) { pool = new JedisMapPool(url); redisPoolMap.put(url,
		 * pool); } Jedis jedis = null; try { jedis = pool.getJedis(); //
		 * System.out.println("Find get jedis!"); if (jedis != null) { String
		 * key = PRE_NODE + id; String lastLinkInfo;
		 * //路链信息格式为：linkID,length,snodeID if (trajBuffer.containsKey(key)) {
		 * lastLinkInfo = trajBuffer.get(key).get(e.get(i)); } else {
		 * lastLinkInfo = jedis.hget(key, e.get(i)); }
		 * 
		 * // System.out.println("Find get lastLinkInfo!"); if (lastLinkInfo ==
		 * null) { System.out.println("cannot get linkInfo:" + id + "," +
		 * e.get(i)); pool.releaseJedis(jedis); continue; } String[] info =
		 * lastLinkInfo.split(","); if (info.length != 3) { System.out.println(
		 * "get linkinfo error!" + lastLinkInfo); pool.releaseJedis(jedis);
		 * continue; } linkInfoBuffer.push(lastLinkInfo); String preNodeID =
		 * info[2];
		 * 
		 * //缓存 HashMap<String, String> trajMap = trajBuffer.get(key); if
		 * (trajMap == null) { trajMap = (HashMap<String, String>)
		 * jedis.hgetAll(key); trajBuffer.put(key, trajMap); }
		 * 
		 * //如果没有找到起点，则继续往前查找，路链信息入栈 HashSet<String> tmpNodes = new
		 * HashSet<String>(); tmpNodes.add(preNodeID); while
		 * (!preNodeID.equals(id)) { lastLinkInfo = trajMap.get(preNodeID); //
		 * lastLinkInfo = jedis.hget(key, preNodeID); // System.out.println(
		 * "Find get while lastLinkInfo!"); if (lastLinkInfo == null) {
		 * System.out.println("preTraj error:" + id + "," + preNodeID);
		 * linkInfoBuffer.clear(); break; } String[] tmp =
		 * lastLinkInfo.split(","); if (tmp.length != 3) { System.out.println(
		 * "preTraj error:" + id + "," + preNodeID); linkInfoBuffer.clear();
		 * break; } linkInfoBuffer.push(lastLinkInfo); preNodeID = tmp[2]; if
		 * (tmpNodes.contains(preNodeID)) { linkInfoBuffer.clear();
		 * System.out.println("Error preTraj:" + id + "," + info[2]); break; }
		 * tmpNodes.add(preNodeID); // System.out.println("Find get preNodeID!"
		 * ); } tmpNodes.clear();
		 * //如果当前link的前一个点为起点，则找到了路径，linkInfoBuffer出栈，保存轨迹
		 * //轨迹格式为：linkID,length,snodeID;linkID,length,snodeID; trajectoryInfo =
		 * getTrajectory(linkInfoBuffer); linkInfoBuffer.clear();
		 * pool.releaseJedis(jedis); // System.out.println("Find release jedis!"
		 * ); break; } else { System.out.println("cannot not get jedis:" + url);
		 * pool.releaseJedis(jedis); } } catch (Exception e1) {
		 * pool.releaseJedis(jedis); System.out.println(
		 * "get preTraj from redis error:" + url); } // finally { // if (jedis
		 * != null) { // pool.releaseJedis(jedis); // } // } }
		 * 
		 * //不过两点间路径是否找到，都要保存，无路径为null lst.add(trajectoryInfo); // // String
		 * info = null; // if(hist.containsKey(id)){ //
		 * //System.out.println("hist"); // info = hist.get(id); // }else{ //
		 * //long t1 = System.currentTimeMillis(); // Query query = new
		 * TermQuery(new Term("id","n"+s.get(i))); // ScoreDoc[] hits =
		 * rtSearcher.search(query, 1).scoreDocs; // if(hits.length==0){ //
		 * //System.out.println(id+ "route is null."); // //long t2 =
		 * System.currentTimeMillis(); //
		 * //System.out.println(id+",rt="+(t2-t1)); // lst.add(null);continue;
		 * // } // info = rtSearcher.doc(hits[0].doc).get("info"); // //long t2
		 * = System.currentTimeMillis(); //
		 * //System.out.println(id+",rt="+(t2-t1)); // hist.put(id, info); // }
		 * // //String info = hitDoc.get("info"); // int index =
		 * info.indexOf(";n"+e.get(i)+","); // // if(index<0){ //
		 * //System.out.println(id+ "->"+e.get(i) +" is null."); //
		 * lst.add(null);continue; // } // String head = info.substring(0,
		 * index); // String end = info.substring(index+1).split(";")[0]; //
		 * String[] infs = end.split(","); // // String parent = infs[2]; // //
		 * String[] ins = head.split(";"); // String lnks =""; // for(int
		 * j=ins.length-1;j>=0;j--){ // //if(ins[j].startsWith("n")){continue;}
		 * // String[] cur = ins[j].split(","); // try{ //
		 * if(cur[3].equalsIgnoreCase(parent)){ //
		 * lnks=";"+cur[0]+","+cur[1]+lnks; // parent = cur[2]; //
		 * if(parent.equalsIgnoreCase("-1")){ // break; // } // } //
		 * }catch(Exception e1){ // e1.printStackTrace(); //
		 * //System.out.println(""); // } // } // lst.add(lnks.substring(1)); }
		 */
		// trajBuffer.clear();
		return lst;
	}

	/**
	 * TODO(功能描述)
	 * 
	 * @param s
	 * @return
	 */
	// private HashMap<Integer, ArrayList<String>> getShardNoSnodeMap(
	// ArrayList<String> s) {
	// // TODO Auto-generated method stub
	// HashMap<Integer, ArrayList<String>> resultMap = new HashMap<Integer,
	// ArrayList<String>>();
	// HashSet<String> snodeSet = new HashSet<String>();
	// for (int i = 0; i < s.size(); i++) {
	// String id = s.get(i);
	// if (snodeSet.contains(id)) {
	// continue;
	// }
	// snodeSet.add(id);
	//
	// Integer shardingNo = getPreTrajShardNo(id);
	// ArrayList<String> snodes = resultMap.get(shardingNo);
	// if (snodes == null) {
	// snodes = new ArrayList<String>();
	// resultMap.put(shardingNo, snodes);
	// }
	// snodes.add(id);
	// }
	// return resultMap;
	// }

	/**
	 * TODO(功能描述)
	 * 
	 * @param linkInfoBuffer
	 * @return
	 */
	private String getTrajectory(Stack<String> linkInfoBuffer) {
		// TODO Auto-generated method stub
		if (linkInfoBuffer.size() == 0) {
			return null;
		}
		StringBuffer sb = new StringBuffer();
		int num = linkInfoBuffer.size();
		for (int i = 0; i < num; i++) {
			sb.append(linkInfoBuffer.pop());
			sb.append(";");
		}
		return sb.toString();
	}

	/**
	 * TODO(功能描述)
	 * 
	 * @param id
	 * @return
	 */
	// private Integer getPreTrajShardNo(String nodeID) {
	// // TODO Auto-generated method stub
	// Long node = Long.parseLong(nodeID);
	// return (int) (node % shardingConfigMap.size());
	// }

	/**
	 * 
	 * @param path
	 * @return
	 */
	// private Neo4JPath getNeo4j(WeightedPath path) {
	// //this.count.put("getNeo4j_w", count.get("getNeo4j_w") + 1);
	// //long t1 = new Date().getTime();
	// double cost = path.weight();
	// List<Neo4JLink> links = new ArrayList<Neo4JLink>();
	//
	// Iterator<Relationship> iterator = path.relationships().iterator();
	// while(iterator.hasNext()) {
	// Relationship rel=iterator.next();
	// String snode = (String)rel.getStartNode().getProperty("nodeid");
	// String enode = (String)rel.getEndNode().getProperty("nodeid");
	// String id = (String)rel.getProperty("linkid") + "";
	// double width = (Float)rel.getProperty("width");
	// float length = (Float)rel.getProperty("length");
	// double speedlimit = (Float)rel.getProperty("speedlimit");
	// int direction = (Integer)rel.getProperty("direction");
	// String kind = (String)rel.getProperty("roadtype");
	// String roadlass = (String)rel.getProperty("roadclass");
	// Neo4JLink neo4JLink = new Neo4JLink(id, width, length, speedlimit,
	// (short)direction, kind, roadlass);
	// neo4JLink.setsNodeid(snode);
	// neo4JLink.seteNodeid(enode);
	// links.add(neo4JLink);
	// }
	// //long t2 = new Date().getTime();
	// //this.time.put("getNeo4j_w", time.get("getNeo4j_w") + (t2 - t1));
	// return new Neo4JPath(cost,links);
	// }
	/**
	 * TODO(功能描述)
	 * 
	 * @param args
	 * @throws Exception
	 */
	public static void main(String[] args) throws Exception {
	
		// // TODO Auto-generated method stub
		// // String str =
		// //
		// "1376582348,116.5270996,39.9413114|1376582350,116.5271116,39.9411991|1376582360,116.5273421,39.9408071|1376582372,116.5275144,39.9407745|1376582384,116.527519,39.9407764|1376582396,116.5275212,39.9407726|1376582408,116.5276929,39.9411622|1376582410,116.5276921,39.9412354|1376583502,116.5277235,39.9413659";
		// // String str =
		// //
		// "1396454370,116.392340,39.907297|1396454385,116.393888,39.907382|1396454397,116.396678,39.907448|1396454407,116.399394,39.907448";
		// // String str =
		// //
		// "120.67427,23.96098,0,-135.8546820314871,1365440725|120.67333,23.96009,30,-154.4316026912092,1365440777|120.67232,23.95815,15,151.12763659230328,1365440807|120.67213,23.95797,11,210.0,1365440837|120.67343,23.9563,38,167.30279191164848,1365440867|120.67419,23.9532,56,-146.96881643396225,1365440897|120.67153,23.94944,62,-101.51716005030053,1365440927|120.66704,23.94895,41,300.0,1365440957|120.6687,23.94891,42,151.69469038489265,1365440987|120.67047,23.94512,65,151.0,1365441017|120.67354,23.94065,74,135.64639065052583,1365441047|120.67805,23.93641,84,158.33518813267276,1365441077|120.68063,23.93044,87,163.51766941046745,1365441107|120.68269,23.92404,94,132.45885878873722,1365441137|120.68823,23.91938,94,138.62173073201834,1365441167|120.69351,23.91387,98,122.55417809231902,1365441197|120.70024,23.90992,98,149.18991419650476,1365441227|120.70432,23.90363,98,137.1826846154151,1365441257|120.70951,23.89848,93,171.26301959012173,1365441287|120.71068,23.89148,96,-172.20846718314868,1365441317|120.70968,23.88476,85,-165.7574911153578,1365441347|120.70801,23.87871,80,-160.05428616433588,1365441377|120.7061,23.87387,40,-164.14944884595567,1365441397|120.7061,23.87387,63,194.0,1365441407|120.70451,23.86872,79,-162.9842311925111,1365441437|120.70257,23.86289,84,-173.671340303098,1365441467|120.70175,23.85609,97,166.94344750121888,1365441497|120.70352,23.84907,96,168.75177134248523,1365441527|120.70504,23.84204,96,160.9851867031921,1365441557|120.70761,23.83518,96,175.3852443857627,1365441587|120.70824,23.828,96,-161.18189283223865,1365441617|120.70571,23.82117,96,-140.75499049039036,1365441647|120.70072,23.81555,97,-154.12330826172453,1365441677|120.69733,23.80912,96,169.10948403214192,1365441707|120.6988,23.80209,96,156.31931832195144,1365441737|120.70196,23.79546,96,161.3597851625325,1365441767|120.70446,23.78864,96,-164.76660473784804,1365441797|120.70243,23.78178,96,-125.94099519249632,1365441827|120.69615,23.77759,96,-90.07814242328215,1365441857|120.68834,23.77758,96,-82.11739675576587,1365441887|120.68049,23.77858,97,-95.06111305201377,1365441917|120.67264,23.77794,97,-111.36596148047519,1365441947|120.66528,23.77529,96,-95.63990840741171,1365441977|120.65747,23.77458,96,-91.42205136613184,1365442007|120.6496,23.7744,96,-90.94640651953786,1365442037|120.64172,23.77428,96,-91.02408547737285,1365442067|120.63383,23.77415,96,-78.40494759706446,1365442097|120.62615,23.7756,96,-84.64560120794964,1365442127|120.61838,23.77627,96,-114.83511781569129,1365442157|120.61129,23.77325,96,-145.29299279285394,1365442187|120.60685,23.76735,97,-163.15184461730638,1365442217|120.60456,23.76039,96,-143.19723266321435,1365442247|120.59987,23.75462,96,-133.6058465329793,1365442277|120.59419,23.74964,96,-176.11023943380363,1365442307|120.59317,23.73583,96,145.93116519545998,1365442367|120.59757,23.72984,96,145.8409544541368,1365442397|120.60197,23.72387,95,168.66252878785403,1365442427|120.60349,23.71689,97,-174.3192760976573,1365442457|120.60271,23.70967,96,177.00671456796948,1365442487|120.60312,23.70245,96,-161.83957755662726,1365442517|120.60068,23.6956,96,-142.13027253626166,1365442547|120.59585,23.68988,96,-149.4489780165694,1365442577|120.59187,23.68367,96,-151.10056001654183,1365442607|120.5881,23.67738,96,-125.98261739591698,1365442637|120.58173,23.67312,96,-132.11698460166377,1365442667|120.57593,23.66829,96,-155.03759468714804,1365442697|120.57264,23.66178,96,-177.28602681567483,1365442727|120.57227,23.65459,96,175.720403870221,1365442757|120.57285,23.64745,94,-175.21935207071485,1365442787|120.57221,23.6404,94,-164.90903648069477,1365442817|120.57029,23.63384,79,-154.46455710321453,1365442847|120.56777,23.62898,65,-147.01031909565344,1365442877|120.56498,23.62502,40,-142.21410432695515,1365442901|120.56498,23.62502,68,212.0,1365442907|120.56116,23.62048,80,-131.1453570783803,1365442937|120.55608,23.61639,88,-121.27018893346036,1365442967|120.54979,23.61287,92,-110.87224310328719,1365442997|120.54259,23.61034,97,-107.78440337290064,1365443027|120.53508,23.60812,97,-123.82709472526697,1365443057|120.5287,23.60418,89,-144.39062730566943,1365443087|120.52469,23.59902,80,-153.09242442522512,1365443117|120.52181,23.59379,81,-144.70628166520703,1365443147|120.51777,23.58853,90,-135.95729278933888,1365443177|120.51245,23.58346,94,-145.71886815763557,1365443207|120.50802,23.57747,94,-161.05586538638028,1365443237|120.50554,23.57081,94,-175.2439342580127,1365443267|120.50491,23.56383,92,179.62751988881618,1365443297|120.50496,23.55674,94,-177.3109387005042,1365443327|120.50461,23.54987,87,-155.070488428711,1365443357|120.50158,23.54386,91,-131.7217397953761,1365443387|120.49624,23.53947,88,-132.16022865463017,1365443417|120.49085,23.53497,91,-148.140874448406,1365443447|120.48686,23.52905,93,-164.22660316163,1365443477|120.48478,23.52226,93,177.48212547094118,1365443507|120.48512,23.51513,91,159.58278924077317,1365443537|120.48778,23.50854,97,149.1367259306311,1365443567|120.49183,23.50229,97,163.81705322417454,1365443597|120.49402,23.49533,98,167.72209805921793,1365443627|120.4957,23.48821,97,163.00155548981016,1365443657|120.49647,23.48665,0,154.0,1365443687|120.50028,23.47439,97,-167.89500975374852,1365443717|120.49862,23.46725,98,-146.24480861014072,1365443747|120.49423,23.46119,98,-134.44642847223247,1365443777|120.48855,23.45605,97,-147.43681910345322,1365443807|120.4843,23.44991,97,-158.8647023624072,1365443837|120.48143,23.44306,97,-148.1562089315026,1365443867|120.47725,23.43685,97,-133.92270757811548,1365443897|120.4715,23.43174,98,-137.88001940434836,1365443927|120.46615,23.42628,98,-152.19589085275163,1365443957|120.46243,23.41977,98,-137.56080898549286,1365443987|120.45705,23.41434,99,-112.80484136654326,1365444017|120.44968,23.41148,98,-102.85270841558648,1365444047|120.44194,23.40985,97,-125.09418803789411,1365444077|120.43551,23.40568,98,-150.47689629597414,1365444107|120.43162,23.39934,97,-167.2712685632092,1365444137|120.42988,23.39223,97,-179.20528557460696,1365444167|120.42977,23.38491,97,169.09917882956577,1365444197|120.43127,23.37772,97,164.13729990284656,1365444227|120.43344,23.37067,97,164.07213287572065,1365444257|120.43561,23.36365,97,164.15702459939612,1365444287|120.43778,23.35659,97,168.45225187583122,1365444317|120.43936,23.34945,97,-172.7642412790562,1365444347|120.43837,23.34225,98,-154.84483015863506,1365444377|120.4351,23.33582,87,-152.2992204481363,1365444407|120.43228,23.33086,58,-162.78823086344292,1365444437|120.43069,23.32612,74,-166.99925929673086,1365444467|120.42919,23.32012,90,-164.57817524693004,1365444497|120.42715,23.31329,98,-146.25734692902708,1365444527|120.42276,23.30722,97,-124.20600819030989,1365444557|120.41623,23.30312,98,-115.4139773632797,1365444587|120.40903,23.29996,97,-126.75378012560844,1365444617|120.40271,23.2956,97,-144.08201976726986,1365444647|120.39806,23.28967,98,-149.45952321158717,1365444677|120.39403,23.28336,97,-135.44820065430645,1365444707|120.38851,23.27818,97,-123.59188684607406,1365444737|120.38191,23.27413,97,-141.99189250811372,1365444767|120.37708,23.26842,97,-171.76049182611598,1365444797|120.37595,23.26121,98,-174.61232730471528,1365444827|120.37521,23.25396,97,-145.1717610373159,1365444857|120.37073,23.24801,98,-136.83372047554656,1365444887|120.36532,23.24268,97,-158.96935403515738,1365444917|120.36252,23.23595,95,-173.73028784930963,1365444947|120.36167,23.2288,95,-162.33292722798885,1365444977|120.35933,23.22201,95,-158.4302300013917,1365445007|120.35649,23.21537,95,-172.36275620085829,1365445037|120.35546,23.20827,95,-178.89368998555344,1365445067|120.35531,23.20109,95,-179.04111626622725,1365445097|120.35518,23.19391,95,-178.96587542995562,1365445127|120.35504,23.18674,95,-178.67413035143593,1365445157|120.35486,23.17955,95,-172.88608874819232,1365445187|120.35388,23.17229,98,-162.68476812865217,1365445217|120.35154,23.16535,96,-153.2947983483016,1365445247|120.34802,23.15888,96,-143.6953206503015,1365445277|120.34338,23.15304,96,-141.80266410873406,1365445307|120.33853,23.14734,96,-153.28590060666156,1365445337|120.33502,23.14089,96,-170.59914584426733,1365445367|120.33374,23.13374,96,-171.3571963148025,1365445397|120.33256,23.12656,98,-158.99649527309657,1365445427|120.3297,23.11967,99,-164.3504917298771,1365445457|120.32758,23.11267,86,-177.67750891364037,1365445487|120.32732,23.10674,77,174.66660098768304,1365445517|120.32798,23.1002,40,176.60337444775735,1365445530|120.32798,23.1002,94,177.0,1365445547|120.32844,23.09303,96,176.63595613627834,1365445577|120.3289,23.08579,96,179.04823378251305,1365445607|120.32903,23.07855,96,-166.7613701565796,1365445637|120.32724,23.07151,96,-155.76674514045152,1365445667|120.32401,23.06487,97,-162.78729674268467,1365445697|120.3217,23.05797,97,-176.17101733940726,1365445727|120.32118,23.05078,96,164.30641171086722,1365445757|120.32329,23.04383,96,157.0306631217789,1365445787|120.32634,23.03717,96,171.61492568761196,1365445817|120.3272,23.03177,33,171.57645336653988,1365445847|120.32728,23.03127,0,171.57645336653988,1365445877";
		// String str =
		// "116.4614185,39.9470842,27,180,1384905535,1|116.4614092,39.9461177,44,177,1384905545,1|116.4614174,39.9448642,50,180,1384905555,1|116.4614071,39.9437237,38,180,1384905565,1|116.461397,39.9426408,40,180,1384905575,1|116.4613881,39.9418257,12,177,1384905585,1|116.4613553,39.9415262,7,186,1384905605,1|116.460912,39.9413835,20,258,1384905615,1|116.4598058,39.9413512,46,267,1384905625,1|116.4582069,39.9413352,50,270,1384905635,1|116.4567245,39.9413233,37,270,1384905645,1|116.4557905,39.9413323,14,270,1384905655,1|116.455417,39.9409934,29,177,1384905726,1|116.4554525,39.9400549,29,177,1384905736,1|116.4554425,39.9393694,16,174,1384905746,1|116.4554362,39.938449,42,180,1384905756,1|116.4554403,39.937388,40,180,1384905766,1|116.4554235,39.9364497,35,180,1384905776,1|116.4554338,39.9357957,0,177,1384905786,1|116.4554115,39.935474,29,177,1384905826,1|116.4554324,39.9344632,29,180,1384905836,1|116.4553839,39.934046,3,177,1384905846,1";
		// String[] gps = str.split("\\|");
		//
		// // GPS a1 = new GPS(116.348,39.865,30.0,new
		// Date().getTime()/1000,50);
		// // GPS a2 = new GPS(116.348,39.863,30.0,new
		// // Date().getTime()/1000+10,50);
		// // GPS a3 = new GPS(116.347,39.859,30.0,new
		// // Date().getTime()/1000+20,50);
		// // GPS a4 = new GPS(116.347,39.857,30.0,new
		// // Date().getTime()/1000+30,50);
		//
		// // List<GPS> ps =new ArrayList<GPS>(Arrays.asList(new
		// // GPS[]{a1,a2,a3,a4}));
		// List<GPS> ps = new ArrayList<GPS>();
		// for (int i = 0; i < gps.length; i++) {
		// String[] s = gps[i].split(",");
		// ps.add(new GPS(Double.parseDouble(s[0]), Double.parseDouble(s[1]),
		// -1, Long.parseLong(s[4]), 0));
		// }
		// // List<GPS> ps = Main.readFile("E:/unmm/115558808.txt");
		// for (int i = 0; i < 1; i++) {
		
		RouteEstLocal re = new RouteEstLocal("172.20.10.141:9001", new HashMap<String, String>(), "1");
		// long t1 = System.currentTimeMillis();
		// List<RouteEstimationLink> r = re.getRoute(ps, false);
		// System.out.println("rst:");
		// for (RouteEstimationLink lnk : r) {
		// System.out.println(lnk.getLinkID() + "," + lnk.getEnterTime()
		// + "," + lnk.getTravelLength() + "," + lnk.getSpeed());
		// }
		// long t2 = System.currentTimeMillis();
		// }

		// Main.writePointShp(ps, "E:/shp/dd-p.shp");
		//
		// Main.writeRouteShp(r, "E:/shp/dd-r-f.shp", "E:/Prj/OD/mm-db-cr-180");
		//
		// System.out.println((t2-t1)/1000);

		String s = "116.323593,40.026538,0.0,1466470715,13,2016/06/21,08:58:35;116.323613,40.026518,0.0,1466470716,11,2016/06/21,08:58:36;116.323623,40.026488,0.0,1466470717,9,2016/06/21,08:58:37;116.323643,40.026468,0.0,1466470718,9,2016/06/21,08:58:38;116.323643,40.026438,0.0,1466470719,10,2016/06/21,08:58:39;116.323663,40.026418,0.0,1466470720,12,2016/06/21,08:58:40;116.323673,40.026388,0.0,1466470721,11,2016/06/21,08:58:41;116.323673,40.026348,0.0,1466470722,9,2016/06/21,08:58:42;116.323693,40.026338,0.0,1466470723,8,2016/06/21,08:58:43;116.323683,40.026318,0.0,1466470724,7,2016/06/21,08:58:44;116.323713,40.026298,0.0,1466470725,4,2016/06/21,08:58:45;116.323713,40.026298,0.0,1466470726,5,2016/06/21,08:58:46;116.323713,40.026288,0.0,1466470727,6,2016/06/21,08:58:47;116.323723,40.026268,0.0,1466470728,7,2016/06/21,08:58:48;116.323723,40.026248,0.0,1466470729,10,2016/06/21,08:58:49;116.323743,40.026218,0.0,1466470730,13,2016/06/21,08:58:50;116.323763,40.026188,0.0,1466470731,15,2016/06/21,08:58:51;116.323783,40.026148,0.0,1466470732,14,2016/06/21,08:58:52;116.323793,40.026118,0.0,1466470733,12,2016/06/21,08:58:53;116.323793,40.026088,0.0,1466470734,9,2016/06/21,08:58:54;116.323803,40.026068,0.0,1466470735,9,2016/06/21,08:58:55;116.323833,40.026038,0.0,1466470736,12,2016/06/21,08:58:56";
		// |1028:1925:0:726:97
		String[] data = s.split(";");
		// TreeMap<Long, GPS> dataMap = new TreeMap<>();
		//
		// String[] tmp = data[0].split(",");
		// Long startLon = Long.parseLong(tmp[0]);
		// Long startLat = Long.parseLong(tmp[1]);
		// int startSpeed = Integer.parseInt(tmp[2]);
		// Long startTime = Long.parseLong(tmp[3]);
		// int startDirection = Integer.parseInt(tmp[4]);

		// GPS gps = new GPS(startLon / 100000.0, startLat / 100000.0,
		// startDirection, startTime * 1000, startSpeed);
		// ps.add(gps);
		TreeMap<Long, GPS> dataMap = new TreeMap<>();
	     dataMap =getGps("d://data//ddd.txt");
//		for (int i = 1; i < data.length; i++) {
//			String[] tmpGps = data[i].split(",");
//			double lon = Double.parseDouble(tmpGps[0]);
//			double lat = Double.parseDouble(tmpGps[1]);
//			int speed = 0;
//			Long time = Long.parseLong(tmpGps[3]);
//			int direction = 0;
//
//			// if (i > data.length - 6) {
//			GPS curGps = new GPS(lon, lat, direction, time, speed);
//			dataMap.put(curGps.time, curGps);
//			// }
//		}

		List<RouteEstimationLink> r = re.getRoute(dataMap, true);
		for (RouteEstimationLink lnk : r) {
			 System.out.println(lnk.getLinkID() + "," + lnk.getEnterTime() +
			 "," + lnk.getTravelLength() + "," + lnk.getSpeed());
		}
	}

	private static TreeMap<Long, GPS> getGps(String file) throws IOException {
		 TreeMap<Long, GPS> gpsMap=new TreeMap<Long, GPS>();
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new FileReader(new File(file)));
		String line="";
		HashSet<String>dataSet=new HashSet<>();
		HashMap<String, String>dataMap=new HashMap<>();
		while((line=br.readLine())!=null){
			String []lineArr=line.split(",");
			double lon=Double.parseDouble(lineArr[0]);
			double lat=Double.parseDouble(lineArr[1]);
			long time=Long.parseLong(lineArr[2]);
			GPS gps=new GPS(lon, lat, 0, time, 0);
			gpsMap.put(time, gps);
		}
		return gpsMap;
	}

	public ArrayList<RouteEstimationLink> isOneTrace(TreeMap<Long, GPS> gpsMap, boolean boolFilter) throws Exception {
		if (this.snodePreTrajMap != null) {
			this.snodePreTrajMap.clear();
			this.snodePreTrajMap = null;
		}
		ArrayList<GPS> gpsList = new ArrayList<>();
		for (Map.Entry<Long, GPS> entry : gpsMap.entrySet()) {
			gpsList.add(entry.getValue());
		}
		int gpsInterval = getInterval(gpsList);

		List<GPS> gpsSeq = boolFilter ? filter(gpsList) : gpsList;

		Cell[] cells = new Cell[gpsSeq.size()];
		GPS lastgps = gpsSeq.get(0);
		for (int i = 0; i < gpsSeq.size(); i++) {
			GPS gps = gpsSeq.get(i);

			String cell = MapUtil.findCell(gps.getLongtitude(), gps.getLatitude());

			Envelope env = MapUtil.getCellBound(cell);
			Polygon polygon = MapUtil.getGPSPolygon(new Coordinate(gps.longtitude, gps.latitude), env);

			cells[i] = new Cell(gps, cell, polygon);
			// 用两点连线的方位角代替点GPS的角度
			if (i > 0) {
				double azm = MapUtil.azimuth(lastgps.longtitude, lastgps.latitude, gps.longtitude, gps.latitude);
				// 处理角度计算异常
				if (azm < -180 || azm > 180) {
					// System.out.println("Error azimuth:" + lastgps.longtitude
					// + " " + lastgps.latitude + " " + gps.longtitude + " " +
					// gps.latitude);
					continue;
				}
				lastgps.setDirection(azm);
				// 起始点用第二点的方位角近似
				if (i == (gpsSeq.size() - 1)) {
					gps.setDirection(azm);
				}
				lastgps = gps;
			}
		}

		long s1 = System.currentTimeMillis();
		try {
			readCell(cells, gpsInterval);
			this.snodePreTrajMap = getNodePreTrajMap(cells);
		} catch (Exception e1) {
			// TODO Auto-generated catch block
			long c1 = System.currentTimeMillis() - s1;
			rdCost = rdCost + c1;
			throw new Exception(e1);
		}
		long c1 = System.currentTimeMillis() - s1;
		rdCost = rdCost + c1;
		// 保存读取的link信息
		HashMap<String, Link> linkIDLinkMap = getLintMap(cells);
		// 保存每条link上的投影信息
		HashMap<String, ArrayList<Projection>> linkProjMap = getLinkProjMap(cells);

		ArrayList<ArrayList<CaPath>> paths = new ArrayList<ArrayList<CaPath>>();
		Cell lastcell = cells[0];

		for (int i = 1; i < cells.length; i++) {
			if (lastcell.getPrj() == null || lastcell.getPrj().size() < 1) {
				lastcell = cells[i];
				continue;
			}
			Projection[] s = new Projection[lastcell.getPrj().size()];
			Cell cur = cells[i];
			if (cur.getPrj() == null || cur.getPrj().size() < 1) {
				continue;
			}

			Projection[] e = new Projection[cur.getPrj().size()];

			lastcell.getPrj().toArray(s);
			cur.getPrj().toArray(e);

			lastcell = cur;

			ArrayList<CaPath> p = getCaPaths(s, e, linkIDLinkMap);

			if (p.size() > 0) {
				paths.add(p);
			} else {
				// System.out.println(i);
			}

		}

		MircoSoftWMap map = new MircoSoftWMap(paths);

		MicroSoftWAStar atar = new MicroSoftWAStar();
		ArrayList<CaPath> finalPath = new ArrayList<CaPath>();
		List<String> finalNodes = new ArrayList<String>();
		double cost = Double.MAX_VALUE;

		int cnt = 0;
		HashSet<String> startEndPair = new HashSet<String>();
		ArrayList<String> pairList = new ArrayList<>();
		for (int i = 0; i < map.getStartNodes().size(); i++) {
			for (int j = 0; j < map.getEndNodes().size(); j++) {
				List<String> nodes = atar.find(map, map.getStartNodes().get(i), map.getEndNodes().get(j));
				String pair = map.getStartNodes().get(i) + "_" + map.getEndNodes().get(j);
				// System.out.println(pair);
				if (nodes != null && !startEndPair.contains(pair)) {
					// for(String nod:nodes){
					// System.out.print(nod);
					// }
					// System.out.println();
					// String line="";
					// for(String nodeSeq:nodes){
					// line+=nodeSeq;
					// }
					// boolean isContain=false;
					// for(String trac:pairList){
					// if(trac.contains(line)){
					// isContain=true;
					// break;
					// }
					// }
					// if(!isContain){
					// cnt++;
					// startEndPair.add(pair);
					// finalNodes = nodes;
					// }
					cnt++;
					startEndPair.add(pair);
					finalNodes = nodes;
				}

			}
		}
		// if (cnt > 1) {
		// return null;
		// }
		// if (cnt == 0) {
		// return null;
		// }
		for (int i = 1; i < finalNodes.size(); i++) {
			finalPath.add(map.getCaPath(finalNodes.get(i - 1), finalNodes.get(i)));
		}

		double lastLinkTravelDis = 0.0;
		long lastLinkGpsTime = 0l;
		ArrayList<RouteEstimationLink> lns = new ArrayList<RouteEstimationLink>();
		for (int i = 0; i < finalPath.size(); i++) {
			CaPath p = finalPath.get(i);

			// 轨迹长度
			double len = p.getPathsLength();

			// 轨迹时长
			long t = (p.getEd().getGps().getTime() - p.getSt().gps.getTime());
			if (t == 0) {
				t = 1;
			}

			// km/h
			long speed = Math.round((len / t) * 3.6);

			// // 道路起点到投影点行驶的时间
			// long ts = 0l;

			// 起点进入时间
			long startt = p.getSt().getGps().getTime() * 1000;

			// 起点路链行驶距离
			double clen = p.getSt().linkLenth - p.getSt().prjDistanceFormSNode;

			try {
				lns.add(new RouteEstimationLink(Long.parseLong(p.getSt().getLinkID()), (int) (clen), startt, (int) speed));

				if (p.getSt().getLinkID().equalsIgnoreCase(p.getEd().getLinkID())) {
					lastLinkTravelDis = p.getEd().prjDistanceFormSNode;
					lastLinkGpsTime = p.getEd().getGps().getTime();
					continue;
				}

				if (p.getPaths() != null) {
					ArrayList<CaPathLink> pa = p.getPaths();
					for (CaPathLink l : pa) {
						long ct = (long) ((clen / len) * t * 1000);
						// 中间路链行驶长度等于link长度
						lns.add(new RouteEstimationLink(Long.parseLong(l.getId()), (int) (l.getLength()), startt + ct, (int) speed));
						// System.out.println(l.getId()+":"+(p.getSt().getGps().getTime()*1000+ct-
						// ts*1000));
						clen += l.getLength();
					}
				}

				long endt = startt + (long) ((clen / len) * t * 1000);

				// 结束link行驶长度等于link长度
				lns.add(new RouteEstimationLink(Long.parseLong(p.getEd().getLinkID()), (int) (p.getEd().getLinkLenth()), endt, (int) speed));

				lastLinkTravelDis = p.getEd().prjDistanceFormSNode;
				lastLinkGpsTime = p.getEd().getGps().getTime();
				// System.out.println(p.getEd().getLinkID()+":"+endt);
				// lns+=","+p.getEd().getLinkID();
				// lns.add(p.getEd().getLinkID());
			} catch (Exception e) {
				DebugTools.println(e.getMessage());
				continue;
			}
		}

		// String lnks = ","+last;
		ArrayList<RouteEstimationLink> lnks = new ArrayList<RouteEstimationLink>();
		if (lns.size() > 0) {
			RouteEstimationLink last = lns.get(0);
			for (int i = 1; i < lns.size(); i++) {
				// System.out.println(lns.get(i).getLinkID()+":"+lns.get(i).getEnterTime());
				if (lns.get(i).getLinkID() != last.getLinkID()) {
					if (lns.get(i).getEnterTime() < last.getEnterTime()) {
						lnks.clear();
						break;
					}
					long speed = Math.round(last.travelLength * 1.0 / (lns.get(i).enterTime - last.enterTime) * 1000 * 3.6);
					last.setSpeed((int) speed);
					last.projList = linkProjMap.get(String.valueOf(last.linkID));
					lnks.add(last);
					last = lns.get(i);
				}

				// last = lns.get(i);
				if (i == lns.size() - 1) {
					last.travelLength = (int) lastLinkTravelDis;
					long speed = Math.round(last.travelLength * 1.0 / (lastLinkGpsTime - last.enterTime / 1000) * 3.6);
					last.setSpeed((int) speed);
					last.projList = linkProjMap.get(String.valueOf(last.linkID));
					lnks.add(last);
				}
			}
		}
		// 投影到link的两端的舍弃
		ArrayList<RouteEstimationLink> resultlnks = new ArrayList<RouteEstimationLink>();
		for (RouteEstimationLink lik : lnks) {

			long linkID = lik.getLinkID();
			System.out.println("niuxinzan123:linkID" + linkID);
			ArrayList<Projection> newproj = new ArrayList<Projection>();
			ArrayList<Projection> proj = lik.projList;
			for (Projection geoProj : proj) {
				double linkLen = geoProj.linkLenth;
				double prjDistanceFormSNode = geoProj.prjDistanceFormSNode;
				if (prjDistanceFormSNode == 0 || prjDistanceFormSNode == linkLen) {
					System.out.println("linkID:" + linkID + " 距離link距離" + prjDistanceFormSNode + " linklen:" + linkLen);
					continue;
				} else {
					newproj.add(geoProj);
				}
			}
			if (newproj.size() != 0) {
				RouteEstimationLink newLik = new RouteEstimationLink(lik.getLinkID(), lik.getTravelLength(), lik.getEnterTime(), lik.getSpeed());
				newLik.projList = newproj;
				resultlnks.add(newLik);
			} else {
				return null;
			}
		}
		return resultlnks;
	}

	private int getDisFromSnode(double lon, double lat, LineString lineString) {
		// TODO Auto-generated method stub

		Point point = MapUtil.getPoint(new Coordinate(lon, lat));
		Coordinate cs = MapUtil.closestPoint(point, lineString);

		Point prjp = MapUtil.getPoint(cs);

		Coordinate coordinates[] = lineString.getCoordinates();
		int size = coordinates.length - 1;

		// 如果投影点是最初和最后一个点，返回-1
		if (equal(prjp.getCoordinate(), coordinates[size]) || equal(prjp.getCoordinate(), coordinates[0])) {
			return -1;
		}

		double distance, prjDistanceFormSNode = 0;

		int i = 0;
		for (i = 0; i < size; i++) {

			distance = MapUtil.calPointDistance(coordinates[i], coordinates[i + 1]);

			LineSegment lineSegment = new LineSegment(coordinates[i], coordinates[i + 1]);
			Coordinate cur = MapUtil.closestPoint2LineSegment(prjp.getCoordinate(), lineSegment);
			if (equal(prjp.getCoordinate(), cur)) {
				distance = MapUtil.calPointDistance(coordinates[i], prjp.getCoordinate());
				prjDistanceFormSNode = prjDistanceFormSNode + distance;
				break;
			}
			prjDistanceFormSNode = prjDistanceFormSNode + distance;
		}

		return (int) prjDistanceFormSNode;
	}
}
